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

P2512 [HAOI2008] 糖果传递

题目描述

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

输入格式

小朋友个数 $n$，下面 $n$ 行 $a_i$。

输出格式

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

输入输出样例 #1

输入 #1

4
1
2
5
4

输出 #1

4

说明/提示

对于 $100\%$ 的数据 $1\le n\le 10^6$，$1\le a_i\le 1.5\times 10^9$。

#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$ 个队员，每个人都有一个实力值 $a_i$。现在，一年一度的编程大赛就要到了，小可可的学校获得了若干个参赛名额，教练决定把学校信息组的 $n$ 个队员分成若干个小组去参加这场比赛。

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

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

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

输入格式

输入有两行：

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

输出格式

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

输入输出样例 #1

输入 #1

7
4 5 2 3 -4 -3 -5

输出 #1

3

说明/提示

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

【数据范围】

对于 $100\%$ 的数据满足：$1\le n\le 100000$，$|a_i|\le 10^9$。

本题共 $10$ 个测试点，编号为 $1\sim 10$，每个测试点额外保证如下：

#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$，表示大臣的人数。

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

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

输出格式

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

输入输出样例 #1

输入 #1

3 
1 1 
2 3 
7 4 
4 6

输出 #1

2

说明/提示

【输入输出样例说明】

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

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

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

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

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

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

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

【数据范围】

对于 $20\%$ 的数据，有 $1\le n\le 10,0<a,b<8$；

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

对于 $60\%$ 的数据，有 $1\le n\le 100$；

对于 $60\%$ 的数据，保证答案不超过 $10^9$；

对于 $100\%$ 的数据，有 $1\le n\le 1,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$ 个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。现在的情况是：T 部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。

输入格式

第一行，一个整数 $N$。

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

输出格式

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

输入输出样例 #1

输入 #1

4
100 200
200 1300
1000 1250
2000 3200

输出 #1

3

说明/提示

对于 $100\%$ 的数据，$1\le N<150000$，$1\le T_1<T_2<2^{31}$。

#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;
}