Codeforces Round #727 (Div. 2) Stable Groups

这里应该写什么

很显然,先把所有学生排序并且分组

然后,把两个组合并

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
int n,m,k,x;
int a[2000001];
int fa[2000001];
int cnt;
int co[3000001]; 
int find(int x){
	return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
} 
signed main(){
	scanf("%lld%lld%lld",&n,&k,&x);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	sort(a+1,a+n+1);
	for(int i=2;i<=n;++i){
		if(a[i]-a[i-1]<=x){
			fa[i]=i-1;
		}else{
			fa[i]=i;
		}
	}
	fa[1]=1;
	for(int i=2;i<=n;++i){
		if(find(fa[i])!=find(fa[i-1])){
			cnt++;
			co[cnt]=(a[i]-a[i-1]-x)/x+(((a[i]-a[i-1])%x)!=0);	
		} 
	}
	cnt++;
	int tem=cnt;
	sort(co+1,co+cnt);
	for(int i=1;i<cnt;++i){
	//	cout<<co[i]<<endl;
		if(k>=co[i]){
			tem--;
			k-=co[i];
		}else
		break;
	}
	cout<<tem;
	return 0;
}
上一篇:Codeforces Round #727 (Div. 2) C. Stable Groups


下一篇:ArrayList去除重复元素 利用 HashSet