当前位置: 首页 > article >正文

P2512糖果传递 P4447分组 P1080国王游戏 P4053建筑抢修

P2512 [HAOI2008] 糖果传递

题目描述

n n n 个小朋友坐成一圈,每人有 a i a_i ai 个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 1 1 1

输入格式

小朋友个数 n n n,下面 n n n a i a_i ai

输出格式

求使所有人获得均等糖果的最小代价。

输入输出样例 #1

输入 #1

4
1
2
5
4

输出 #1

4

说明/提示

对于 100 % 100\% 100% 的数据 1 ≤ n ≤ 1 0 6 1 \leq n\le 10^6 1n106 1 ≤ a i ≤ 1.5 × 1 0 9 1 \leq a _ i \leq 1.5 \times 10 ^ 9 1ai1.5×109

#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N],c[N],n;

int main(){
	cin >> n;
	for(int i = 1; i <= n ;i++){
		cin >> a[i];
		b+=a[i];
		b = b/n;
	}	
	for(int i = 2; i <= n; i++ ){
		c[i] = c[i-1]+a[i-1]-b; 
	}
	sort(c+1,c+1+n);
	for(int i = 1; i <= n; i++ ){
		ans+=abs(c[i]-c[(n+1)/2]);
	}
	cout << ans;
	return 0;
}

P4447 [AHOI2018初中组] 分组

题目描述

小可可的学校信息组总共有 n n n 个队员,每个人都有一个实力值 a i a_i ai。现在,一年一度的编程大赛就要到了,小可可的学校获得了若干个参赛名额,教练决定把学校信息组的 n n n 个队员分成若干个小组去参加这场比赛。

但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队,于是要求分成的每个小组的队员实力值连续,同时,一个队不需要两个实力相同的选手。举个例子: [ 1 , 2 , 3 , 4 , 5 ] [1, 2, 3, 4, 5] [1,2,3,4,5] 是合法的分组方案,因为实力值连续; [ 1 , 2 , 3 , 5 ] [1, 2, 3, 5] [1,2,3,5] 不是合法的分组方案,因为实力值不连续; [ 0 , 1 , 1 , 2 ] [0, 1, 1, 2] [0,1,1,2] 同样不是合法的分组方案,因为出现了两个实力值为 1 1 1 的选手。

如果有小组内人数太少,就会因为时间不够而无法获得高分,于是小可可想让你给出一个合法的分组方案,满足所有人都恰好分到一个小组,使得人数最少的组人数最多,输出人数最少的组人数的最大值。

注意:实力值可能是负数,分组的数量没有限制。

输入格式

输入有两行:

第一行一个正整数 n n n,表示队员数量。
第二行有 n n n 个整数,第 i i i 个整数 a i a_i ai 表示第 i i i 个队员的实力。

输出格式

输出一行,包括一个正整数,表示人数最少的组的人数最大值。

输入输出样例 #1

输入 #1

7
4 5 2 3 -4 -3 -5

输出 #1

3

说明/提示

【样例解释】
分为 2 2 2 组,一组的队员实力值是 { 4 , 5 , 2 , 3 } \{4, 5, 2, 3\} {4,5,2,3},一组是 { − 4 , − 3 , − 5 } \{-4, -3, -5\} {4,3,5},其中最小的组人数为 3 3 3,可以发现没有比 3 3 3 更优的分法了。

【数据范围】

对于 100 % 100\% 100% 的数据满足: 1 ≤ n ≤ 100000 1\leq n\leq 100000 1n100000 ∣ a i ∣ ≤ 1 0 9 |a_i|\leq10^9 ai109

本题共 10 10 10 个测试点,编号为 1 ∼ 10 1\sim10 110,每个测试点额外保证如下:

测试点编号数据限制
1 ∼ 2 1\sim2 12 n ≤ 6 , 1 ≤ a i ≤ 100 n\leq 6, 1\leq a_i \leq 100 n6,1ai100
3 ∼ 4 3\sim4 34 n ≤ 1000 , 1 ≤ a i ≤ 1 0 5 n\leq 1000, 1\leq a_i\leq 10^5 n1000,1ai105 a i a_i ai 互不相同
5 ∼ 6 5\sim6 56 n ≤ 100000 , a i n\leq 100000, a_i n100000,ai 互不相同
7 ∼ 8 7\sim8 78 n ≤ 100000 , 1 ≤ a i ≤ 1 0 5 n\leq 100000, 1\leq a_i \leq10^5 n100000,1ai105
9 ∼ 10 9\sim 10 910 n ≤ 100000 , − 1 0 9 ≤ a i ≤ 1 0 9 n\leq 100000, -10^9 \leq a_i \leq 10^9 n100000,109ai109
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N],n;
int q[N],siz[N],cnt;

int main(){
	cin >> n;
	for(int i = 1; i <= n ;i++)cin >> a[i];
	sort(a+1,a+1+n);
	q[0] = 2e9;
	
	for(int i = 1,k; i <= n; i++ ){
		//找到小于a[i]-1的最后一组 
		k = upper_bound(q+1,q+1+cnt,a[i]-1)-q-1;
		if(q[k] == a[i]-1)q[k] = a[i],siz[k]++;
		else q[++cnt] = a[i],siz[cnt] = 1; 
	}
	int ans = 1e9;
	for(int i=1; i <= cnt ;i++)ans = min(ans,siz[i]);
	cout << ans;
	
	return 0;
}

P1080 [NOIP 2012 提高组] 国王游戏

题目描述

恰逢 H 国国庆,国王邀请 n n n 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这 n n n 位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。

输入格式

第一行包含一个整数 n n n,表示大臣的人数。

第二行包含两个整数 a a a b b b,之间用一个空格隔开,分别表示国王左手和右手上的整数。

接下来 n n n 行,每行包含两个整数 a a a b b b,之间用一个空格隔开,分别表示每个大臣左手和右手上的整数。

输出格式

一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

输入输出样例 #1

输入 #1

3 
1 1 
2 3 
7 4 
4 6

输出 #1

2

说明/提示

【输入输出样例说明】

1 1 1 2 2 2 3 3 3 这样排列队伍,获得奖赏最多的大臣所获得金币数为 2 2 2

1 1 1 3 3 3 2 2 2 这样排列队伍,获得奖赏最多的大臣所获得金币数为 2 2 2

2 2 2 1 1 1 3 3 3 这样排列队伍,获得奖赏最多的大臣所获得金币数为 2 2 2

按$ 2$、 3 3 3、$1 $这样排列队伍,获得奖赏最多的大臣所获得金币数为 9 9 9

3 3 3 1 1 1、$2 $这样排列队伍,获得奖赏最多的大臣所获得金币数为 2 2 2

按$ 3$、 2 2 2 1 1 1 这样排列队伍,获得奖赏最多的大臣所获得金币数为 9 9 9

因此,奖赏最多的大臣最少获得 2 2 2 个金币,答案输出 2 2 2

【数据范围】

对于 20 % 20\% 20% 的数据,有 1 ≤ n ≤ 10 , 0 < a , b < 8 1≤ n≤ 10,0 < a,b < 8 1n10,0<a,b<8

对于 40 % 40\% 40% 的数据,有$ 1≤ n≤20,0 < a,b < 8$;

对于 60 % 60\% 60% 的数据,有 1 ≤ n ≤ 100 1≤ n≤100 1n100

对于 60 % 60\% 60% 的数据,保证答案不超过 1 0 9 10^9 109

对于 100 % 100\% 100% 的数据,有 1 ≤ n ≤ 1 , 000 , 0 < a , b < 10000 1 ≤ n ≤1,000,0 < a,b < 10000 1n1,000,0<a,b<10000

NOIP 2012 提高组 第一天 第二题

#include<bits/stdc++.h>
using namespace std;
struct node{
	int a,b;
	bool operator<(node &t){
		return a*b < t.a*t.b;
		}//a*b最大则所获得的奖赏越多 
}p[1005];
int m[4005],a[4005],t[4005];//m乘积,t便于存储,a储存答案 
long long lm,la,lt; 
void div(int m[],int b,int t[]){
	for(int i = 1; i <= lt; i++)t[i] = 0;
	int r = 0;
	for(int i = lm;i >= 1; i++){
		r = r*10 +m[i];//被除数 
		t[i] = r/b;
		r%=b;		
	}
	lt = lm;
	while(t[lt] == 0 && lt > 1)lt--; 
}
void mul(int m[],int b,int t[]){
	for(int i = 1; i <= lt; i++)t[i] = 0;
	for(int i = 1; i <= lm; i++)t[i] += m[i]*b;
	lm += 4;
	for(int i = lm;i >= 1; i--){
		t[i+1] += t[i]*b/10;
		t[i]%=10;
	}
	while(t[lm]==0 && lm>1)lm--;
}
bool cmp(int a[],int t[]){
	if(la!=lt)return la<lt;
	for(int i =lt; i ; i--){
		if(a[i]!=t[i])return a[i]<t[i];
		return false;
	}
}
void upd(int a[],int t[]){
	if(cmp(a,t)){
		for(int i = lt;i;i--){
			a[i] = t[i];
			la = lt;
		}
	}
}
int main(){
	int n;
	cin >> n;
	for(int i = 0;i <= n; i++){
		cin >> p[i].a >> p[i].b;
	}
	sort(p+1,p+n+1);
	m[++lm] = p[0].a;//最开始 
	for(int i = 1; i <= n; i++){
		div(m,p[i].b,t);
		upd(a,t);
		mul(m,p[i].a,t);
	}	
	for(int i = la; i ; i--)cout << a[i];
	return 0;
}

P4053 [JSOI2007] 建筑抢修

题目描述

小刚在玩 JSOI 提供的一个称之为“建筑抢修”的电脑游戏:经过了一场激烈的战斗,T 部落消灭了所有 Z 部落的入侵者。但是 T 部落的基地里已经有 N N N 个建筑设施受到了严重的损伤,如果不尽快修复的话,这些建筑设施将会完全毁坏。现在的情况是:T 部落基地里只有一个修理工人,虽然他能瞬间到达任何一个建筑,但是修复每个建筑都需要一定的时间。同时,修理工人修理完一个建筑才能修理下一个建筑,不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕,这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序,以抢修尽可能多的建筑。

输入格式

第一行,一个整数 N N N

接下来 N N N 行,每行两个整数 T 1 , T 2 T_1,T_2 T1,T2 描述一个建筑:修理这个建筑需要 T 1 T_1 T1 秒,如果在 T 2 T_2 T2 秒之内还没有修理完成,这个建筑就报废了。

输出格式

输出一个整数 S S S,表示最多可以抢修 S S S 个建筑。

输入输出样例 #1

输入 #1

4
100 200
200 1300
1000 1250
2000 3200

输出 #1

3

说明/提示

对于 100 % 100 \% 100% 的数据, 1 ≤ N < 150000 1 \le N < 150000 1N<150000 1 ≤ T 1 < T 2 < 2 31 1 \le T_1 < T_2 < 2^{31} 1T1<T2<231

#include<bits/stdc++.h>
using namespace std;

struct node{
  int a,b; //修理时间,报废时间
  bool operator<(node &x){
    return b<x.b;
  }
}t[150005];
priority_queue<int> q;//维护修理时间

int main(){
	int n;
  	cin >> n;
  for(int i=1; i<=n; i++)
    cin >> t[i].a >> t[i].b;
  sort(t+1, t+1+n);
  
  long long sum=0; //修理时间之和
  int ans=0;
  for(int i=1; i<=n; i++){
    sum+=t[i].a;
    q.push(t[i].a);
    if(sum<=t[i].b) //能修,则ans+1
      ans++;
    else //不能修,则抛弃最长修理时间
      sum-=q.top(),q.pop();
  }
  cout << ans;
  return 0;
}

http://www.kler.cn/a/587553.html

相关文章:

  • Python 字节码深度历险:dis 模块揭秘与性能优化实战
  • 深入探讨RAID 5的性能与容错能力:实验与分析(磁盘阵列)
  • Vue 中的 MVVM、MVC 和 MVP 模式深度解析
  • Java数据结构第二十三期:Map与Set的高效应用之道(二)
  • 深度迁移学习实战指南:从理论到产业级应用
  • 安装 MongoDB 的步骤(Windows / macOS / Linux)
  • Excel表一键查询工具
  • 简要分析NETLINK_USER参数
  • springboot系列十五:SpringBoot整合MyBatis, MyBatis-Plus
  • 【数据结构】数据结构,算法 概念
  • ctfshow-萌新赛刷题笔记
  • 路由器与防火墙配置命令
  • 【大模型技术】怎么用agent和prompt工程实现用户的要求?
  • Windows根据文件名批量在文件夹里查找文件并复制出来,用WPF实现的详细步骤
  • LLM - Dify(1.0.1)搭建本地私有RAG知识库完整指南
  • 【观察】拓展大模型应用交付领域“新赛道”,亚信科技为高质量发展“加速度”...
  • Flutter框架开发的安卓App的抓包以及Frida安装和hook使用教程
  • 基于yolo11+flask打造一个精美登录界面和检测系统
  • WPF Prism事件聚合器EventAggregator
  • 代码随想录二刷|图论11