题解：P14915 「QFOI R3」算法竞赛

· · 题解

数的顺序不影响结果，我们先把数组排序。

对于样例 1，我们依次往队伍中加入 3,3,4，组成了一支合法的队伍。对于下一个队伍，加入 6 后我们无法加入 9，于是我们依次添加 7,8 与 6 构成一组，9 则需要再补两个数和它构成一组，答案就是 4。

对于样例 2，我们依次往队伍中加入 3,3,4，组成了一支合法的队伍。对于下一个队伍，加入 6 后我们无法加入 9，此时我们添加 8，发现 9-8\le 2，则 6,8,9 构成了一组，答案就是 1。

我们发现，我们想要加入 a_i 时发现 a_i-a_{i-1}>d，则依次在 a_{i-1} 后面插入 a_{i-1}+d,a_{i-1}+2d,...,a_{i-1}+xd，直到能够使 a_i 加入这个队伍或者把这个队伍填满。

至于为什么每次都要 +d，我们的目标是要让加入的数尽可能少，所以我们每次加数要尽可能地减小 a_i 与新加入数的差，让 a_i 尽早加入队伍。

记录当前队伍的人数 tot，若 tot=k 则新建一个队伍，若发现 a_i-a_{i-1}>d 则循环模拟上述过程，否则令 tot=tot+1。可以得 60 分，代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k,d,a[N],tot,ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>k>>d;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        if(tot==0)tot++;
        else if(a[i]-a[i-1]<=d){
            tot++;
            if(tot==k)tot=0;
        }
        else{
            int pre=a[i-1];
            while(1){
                pre+=d;
                tot++;
                ans++;
                if(tot==k){
                    tot=0;
                    break;
                }
                if(a[i]-pre<=d)break;
            }
            if(tot){
                tot++;
                if(tot==k)tot=0;
            }
            else tot++;
        }
    }
    if(tot!=k&&tot)ans+=k-tot;
    cout<<ans;
    return 0;
}

考虑优化：我们其实要找到一个最小的 x，使得 a_i-(a_{i-1}+xd)\le d，整理得 x\ge \frac{a_i-a_{i-1}}{d}-1，即 x=\lceil \frac{a_i-a_{i-1}}{d}\rceil -1。注意判断当前队伍加上 x 个数后是否超员，以及 d=0 的情况。

代码如下，可供参考：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,k,d,a[N],tot,ans;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>k>>d;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        if(tot==0)tot++;
        else if(a[i]-a[i-1]<=d){
            tot++;
            if(tot==k)tot=0;
        }
        else{
            if(d==0)ans+=k-tot,tot=0;
            else{
                int x=(a[i]-a[i-1]+d-1)/d;
                x--;
                if(tot+x>=k)ans+=k-tot,tot=0;
                else{
                    tot+=x;
                    ans+=x;
                }   
            }
            tot++;
            if(tot==k)tot=0;
        }
    }
    if(tot!=k&&tot)ans+=k-tot;
    cout<<ans;
    return 0;
}