Codeforces Round #727 (Div. 2) C. Stable Groups

题目大意:
有n个学生,第i个学生的水平是ai。你需要把学生分成若干小组。在一组学生的水平排序数组中,相邻的两个元素相差不超过x

教师最多可以邀请k名任意水平的学生
找出教师可以从所有学生(包括新邀请的学生)组成的稳定小组的最小数量。

Examples
input
8 2 3
1 1 5 8 12 13 20 22
output
2
input
13 0 37
20 20 80 70 70 70 420 5 1 5 1 60 90
output
3


首先我们可以将学生按水平从小到大排序,然后贪心将其分组,在不加入学生的情况下,这样分组是最优的。

然后考虑加入学生
每次将两个组合并需要插入一定数量的学生,每次都是对答案减一

所以我们可以处理出每两个组合并需要的学生数
排序,优先合并需要少的,这样就可以保证答案最小了

AC代码:

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int maxn=2e6+3;
ll a[maxn];
ll b[maxn];
int main(){
	int n;
	ll k,x;
	scanf("%d %lld %lld",&n,&k,&x);
	for(int i=1;i<=n;++i)
		scanf("%lld",&a[i]);
	sort(a+1,a+n+1);
	int tot=0;
	for(int i=2;i<=n;++i){
		if(a[i]-a[i-1]>x){
			b[++tot]=(a[i]-a[i-1]-1)/x;
		}
	}
	int sum=tot+1;
	sort(b+1,b+tot+1);
	for(int i=1;i<=tot;++i){
		if(k>=b[i]){
			sum--;
			k-=b[i];
		}
		else break; 
	} 
	printf("%d",sum);
	return 0;
} 
上一篇:神经网络模型保存下载model.state_dict()等用法和功能


下一篇:Codeforces Round #727 (Div. 2) Stable Groups