标签 ： DP
题目链接
http://codeforces.com/contest/985/problem/E
题意
把(n)个数分成多组,使得每组包含至少(k)个元素,且每组中的任意两个元素之差不超过(d)
分析
- 很巧妙的DP
- 我们使用
dp[i]来表示（如果不存在i+1~n个元素的时候）前i个能否满足题目条件放入boxes中。 dp[i]为true当且仅当存在一个j满足-
[]
egin{aligned}
a[j+1] geq a[i]-d
dp[j]=true
i-j geq k
end{aligned}
ight.
[也就是说我们存在一个`j`使得可以把前`j`个在满足题目条件的情况下放入盒子。然后j+1~i个元素可以放到一个盒子里。
## 代码
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=500050;
int sum[maxn],n,k,d,a[maxn];
bool f[maxn];
queue<int> q,s;
int main(){
scanf("%d%d%d", &n,&k,&d);
for(int i = 1; i <= n; ++i) scanf("%d",a+i);
sort(a+1,a+1+n);
q.push(1);
for(int i = 1; i <= n; ++i){
while(!s.empty()&&a[s.front()]<a[i]-d) s.pop();
s.push(i);
int p = s.front();
while(!q.empty()&&q.front()<p) q.pop();
if(!q.empty()&&i-q.front()+1>=k) f[i]=true,q.push(i+1);
}
cout << (f[n]?"YES":"NO") << endl;
return 0;
}
```]