under 题解 CF985E

---

题意

给定大小为 $n$ 的可重集合 $T$ 与整数 $k, d$，求若干互不相交的可重集合 $S_i$，使得

• $\bigcup S_i = T$
• $|S_i| \ge k$
• $\max\{S_i\} - \min\{S_i\} \le d$

判断能否找到一组合法的解。

• $1 \le k, n \le 5 \times 10^5, \ d \le 10^9$

解题

初看题面，很容易想到一种贪心做法：

从小到大排序，每次选择第一个未被选用的数 $a_i$，将 $a_i \sim a_i + d$ 的所有数划分到同一集合中。

不难想到这种算法是错误的。考虑数据 4 2 1 1 2 2 3，就可以把这种算法卡掉。对于这组数据，唯一合法的划分方案为 $S_1 = \{1, 2\}, S_2 = \{2, 3\}$。上述贪心将两个元素 2 划分到了同一个集合中，导致 3 无法分配。

自然想到利用 dp。

令 f[i] 表示前 i 个数有无合法划分方案。转移时利用队列，考虑 a[i] - a[i - K] 的差值与 k 的大小关系。细节见代码。

代码

#include<algorithm>
#include<bitset>
#include<iostream>
#include<queue>

std::bitset<500003> f;
int N, K, D, z[500003];
std::queue<int> q;

bool dp() {
  f[0] = 1;
  for (int i = K; i <= N; ++i) {
    if (f[i - K]) q.push(z[i - K + 1]);
    while (q.size() && z[i] - q.front() > D)
      q.pop();
    f.set(i, (bool)q.size());
  }
  return f[N];
}

int main() {
  std::cin >> N >> K >> D;
  for (int i = 1; i <= N; ++i)
    std::cin >> z[i];
  std::sort(z + 1, z + N + 1);
  std::cout << (dp() ? "YES" : "NO");
  return 0;
}