/*
dp[i]=0|1 表示前i是否可以被成功分组，
dp[i+1]能够变成1的三个条件
1：j∈[0,i-k]里存在dp[j]=1
2：dp[j]=1
3：a[i+1]-a[j+1]<=d
即可以把[j+1,i+1]分为一组，放在前j个之后
先进行排序，暴力的复杂度是o(n*n)
其实每次求dp[i]时，只要考虑区间[pos,i-k]的dp即可，pos为第一个比a[i]-d小的坐标再-1（为什么要-1，因为新的段是接在前面的段后面，所以其实是从a[i]-d的前面开始算起）
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 5000005
int d,dp[maxn],a[maxn],n,k;
int bit[maxn];
void update(
int x,
int v){
while(x<=
n){
bit[x]+=
v;
x+=(x&-
x);
}
}
int query(
int x){
int res=
0;
while(x){
res+=
bit[x];
x-=(x&-
x);
}
return res;
}
int main(){
cin>>n>>k>>
d;
for(
int i=
1;i<=n;i++)cin>>
a[i];
sort(a+
1,a+
1+
n);
for(
int i=
1;i<=n;i++
){
if(i<k)dp[i]=
0;
else if(a[i]-a[
1]<=d)dp[i]=
1;
else {
int pos=lower_bound(a+
1,a+
1+n,a[i]-d)-a-
1;//这里要注意一下
dp[i]=(query(i-k)-query(pos-
1))>
0;
}
if(dp[i])update(i,
1);
}
if(dp[n])puts(
"YES");
else puts(
"NO");
}
转载于:https://www.cnblogs.com/zsben991126/p/11169130.html
