『DP·单调队列』CodeForces - 985E Pencils and Boxes

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$

纠正luogu的一个mistake:是$|a_i?a_j|\le d.$

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

我们可以采用DP的思想，设$f[i]$表示到$i$为止分成若干组的可行性。

显然我们可以通过排序，想原来的序列分成连续的几段。

那么就有：$$f[i]|=f[j](i?j<k且a_i?a_{j+1}\le d)$$

我们来考虑一下如何快速的解决这些限制。

由于数据元素单调递增，因此我们可以来维护一个单调队列。

• 对于限制$i?j<k$来说，只要满足$f[i?k]=1$就将$i?k+1$加入队列。
• 弹出首位差值过大的队头，直到满足条件位置，即$a[i]?a[\mathrm{f}\mathrm{r}\mathrm{o}\mathrm{n}\mathrm{t}]\le d$为止。

代码如下：

#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>using namespace std;
const int N = 6e5;int n, m, k, d;
int a[N], f[N];queue<int>q;int read(void)
{
    int s = 0, w = 0; char c = getchar();while (c < '0' || c > '9') w |= c == '-', c = getchar();while (c >= '0' && c <= '9') s = s*10+c-48, c = getchar();return w ? -s : s;
}int main(void)
{
    n = read(), k = read(), d = read();for (int i=1;i<=n;++i) a[i] = read();sort(a+1,a+n+1);f[0] = 1;for (int i=k;i<=n;++i){
    if (f[i-k]) q.push(i-k+1);while (q.size() && a[i]-a[q.front()] > d) q.pop();f[i] = !q.empty();}puts(f[n] ? "YES" : "NO");return 0;
}