/*
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=;
while(x){
res+=bit[x];
x-=(x&-x);
}
return res;
} int main(){
cin>>n>>k>>d;
for(int i=;i<=n;i++)cin>>a[i];
sort(a+,a++n); for(int i=;i<=n;i++){
if(i<k)dp[i]=;
else if(a[i]-a[]<=d)dp[i]=;
else {
int pos=lower_bound(a+,a++n,a[i]-d)-a-;//这里要注意一下
dp[i]=(query(i-k)-query(pos-))>;
}
if(dp[i])update(i,);
}
if(dp[n])puts("YES");
else puts("NO");
}

最新文章

  1. 为什么你不应该使用 MongoDB
  2. MySQL性能优化的最佳经验,随时补充
  3. oracle 常见恢复
  4. macbook 我们需要买吗
  5. Training little cats_矩阵快速幂
  6. boost 编译
  7. 排序算法(冒泡,选择,快速)Java 实现
  8. Excel操作 Microsoft.Office.Interop.Excel.dll的使用
  9. 初涉JavaScript模式系列 阶段总结及规划
  10. iOS 删除相册中照片--来自简书
  11. CentOS服务器上的 git 包版本控制
  12. CopyOnWriteArrayList集合排序异常问题
  13. vim美化基本配置
  14. 提取C3D视频特征(官方文档&amp;实践)
  15. Oracle 使用序列实现自增列 及重置序列
  16. layer 关闭当前弹出层
  17. CentOS卸载通过yum安装的软件
  18. MFS故障测试及维护总结
  19. 如何使用网格搜索来优化深度学习模型中的超参数(Keras)
  20. unigui如何连接数据库

热门文章

  1. string参考
  2. flutter进行自动编译操作步骤
  3. Java——main()方法
  4. 基于SpringBoot的花里胡哨配置
  5. 深入浅出 Vue.js 第九章 解析器---学习笔记
  6. golang 读取 ini配置信息
  7. mac 安装 pymssql 报错
  8. MakeDown渲染出错
  9. HBase 永久RIT(Region-In-Transition)问题
  10. IceCTF-Matrix