Lisa

尺取法搞一波

然后前缀和优化一波

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int a[500005];
bool f[500005];
int n,k,d;
int sum[500005];
int main(){
//  ios::sync_with_stdio(false);
    scanf("%d%d%d",&n,&k,&d);
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    int l=1;
    f[0]=1;
    sum[0]=1;
    for(int i=1;i<=n;++i){
        while(a[l]+d<a[i]) l++;
    //  for(int j=l;i-j+1>=k;++j){
    //      if(f[j-1]) {
    //          f[i]=1;
    //          break;
    //      }
    //  }
        if(i-k<0) {
        sum[i]=sum[i-1]+f[i];
        continue;
        }
        if(l-2<0){
            if(sum[i-k])
            f[i]=1;
        }else
        if(sum[i-k]-sum[l-2]>0){
            f[i]=1;
        }
            sum[i]=sum[i-1]+f[i];
    }
//  for(int i=1;i<=n;++i){
//      cout<<f[i]<<" "; 
//  }
    if(f[n]) cout<<"YES";
    else cout<<"NO";
    return 0;
}