Educational Codeforces Round 44 (Rated for Div. 2) E. Pencils and Boxes

E. Pencils and Boxes

这场cf D题的题意确是有点毒，于是乎比赛时我滚去做了E。

E题意：给你n$n$个数字，让你将他们分成几个集合，集合中至少有k$k$个数字，且集合中最大于最小的差值小于等于d$d$。

直观的想法，直接先sort$sort$一遍，由题意我们可以很容易发现如果可分，那么前k$k$个必定在在一个集合中，那么之后就是一个贪心的问题了。
根据要求我们还可以得出另一个小推论：对于给定数组，在保证前m$m$个集合都是可划最优size$size$的情况下，当前下一个划分的集合的size$size$越小差值越小。

然后，还有一个容易得到的小推论：对于任意一个以满足条件的集合，若是他的size$size$足够大，从他里划分出的任意子集（size>=k$size>=k$)也都是满足题意的，所以说假设一个数组他是可分得，那么我们只要保证剩下的数的size$size$，前面的集合的size$size$可以尽量大，并且这不影响后面的数。如果该数组是不可分的，保证的剩下的size$size$个必定是不满足的。

那么现在我们是需要判定是否可以一直贪心的划分到最后一位即可。

下面的解释直接写注释了，不然讲起来比较麻烦。

#include<cstdio>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<limits.h>
#include<string.h>
#include<map>
#include<list>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define inf int(0x3f3f3f3f)
#define mod int(1e9+7)
#define eps double(1e-6)
#define pi acos(-1.0)
#define lson  root << 1
#define rson  root << 1 | 1


int n,k,d;

ll a[500005];

int vis[500005];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k>>d;
    memset(vis,0,sizeof(vis));
    vis[0]=1;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    int cnt=1;
    int pre=0;
    int las=0;
    for(int i=k;i<=n;i++)
    {
        while(pre<=las&&a[i]-a[pre+1]>d)//pre<=las并且i从k开始即控制了size>=k
        {
            if(vis[pre])
                cnt--;
            pre++;
        }
        if(cnt>0)//cnt>0等价于集合size>=k
            vis[i]=1;
        las++;
        if(vis[las])
            cnt++;
    }
    if(vis[n])
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
}