第一眼上去以为二分答案,结果是贪心。
先扫一遍贪心得到组数最小的分配方案(不插入学生)。
然后将组与组之间的差排序,贪心考虑插人。
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
ll n, k, x, a[200005], prob[200005], cnt;
ll cmp(int aa, int bb)
{
return (a[aa + 1] - a[aa]) < (a[bb + 1] - a[bb]);
}
int main()
{
scanf("%lld%lld%lld", &n, &k, &x);
for(ll i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
}
sort(a + 1, a + n + 1);
ll tot = 1;
for(ll i = 2; i <= n; i++)
{
if(a[i] - a[i - 1] > x)
{
prob[++cnt] = i - 1;
tot++;
}
}
sort(prob + 1, prob + cnt + 1, cmp);
for(ll i = 1; i <= cnt; i++)
{
if(k >= ((a[prob[i] + 1] - a[prob[i]] - 1) / x))
{
k -= ((a[prob[i] + 1] - a[prob[i]] - 1) / x);
tot--;
}
}
printf("%lld", tot);
return 0;
}