题解 CF985E

贪心+DP。

先从小到大排序。

定义 \(f_i\) 表示序列 \([1,i]\) 能否分组。

转移为 \(f_i|=f_j[a_i-a_j\le d,j\le i-k+1]\)。

右区间可以直接算出来，左区间可以二分或根据单调性弄个指针。

定义 \(sum_i=\sum\limits_{t=1}^{i}f_t\)，前缀和减一下判断是否为正即可。

复杂度 \(O(n\log n)\) 或 \(O(n)\)。

code:

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int sum[N],n,k,d,a[N];
int main(){
  ios::sync_with_stdio(false);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);
  int ok,l,r;
  for(int i=1;i<=n;++i){
    ok=0;
    if(i>=k&&a[i]-a[1]<=d)ok=1;
    l=lower_bound(a+1,a+n+1,a[i]-d)-a;r=i-k+1;
    if(l<=r&&sum[r-1]-sum[max(l-2,0)])ok=1;
    sum[i]=sum[i-1]+ok;
  }
  if(ok)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  return 0;
}