纠正luogu的一个mistake:是 ∣ a i − a j ∣ ≤ d . |a_i-a_j|\le d. ∣ai−aj∣≤d.
我们可以采用DP的思想，设 f [ i ] f[i] f[i]表示到 i i i为止分成若干组的可行性。
显然我们可以通过排序，想原来的序列分成连续的几段。
那么就有： f [ i ] ∣ = f [ j ] ( i − j < k 且 a i − a j + 1 ≤ d ) f[i]|=f[j](i-j<k且a_i-a_{j+1}\le d) f[i]∣=f[j](i−j<k且ai−aj+1≤d)
我们来考虑一下如何快速的解决这些限制。
由于数据元素单调递增，因此我们可以来维护一个单调队列。
对于限制 i − j < k i-j<k i−j<k来说，只要满足 f [ i − k ] = 1 f[i-k]=1 f[i−k]=1就将 i − k + 1 i-k+1 i−k+1加入队列。弹出首位差值过大的队头，直到满足条件位置，即 a [ i ] − a [ f r o n t ] ≤ d a[i]-a[\mathrm{front}]\le d a[i]−a[front]≤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; }