题目大意:
有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;
}