CF1886E 题解

· · 题解

把题意抽象成，给你长为 n 的序列 a 和长为 m 的序列 b，初始有 m 个空集合（可重集），a 中的每个元素至多被分到 m 个集合中的一个。要求最后第 i 个集合 T_i 不为空，且 \forall x \in T_i, x \ge \frac{b_i}{|T|}。要求构造方案或报告无解。

先把 a 从大到小排序。发现最后每个集合分到的一定是在排序后序列的一段区间。因为 11121222 显然比 11112222 劣。

然后考虑一个从前往后分配集合元素的可行性 dp。设 f_{i, S} 为当前 a 中 [1, i] 的元素被分配完了，S 为已经考虑完的集合的编号集合为 S。转移枚举下一段的右端点 j，枚举 [i + 1, j] 被分到第 k 个集合，有 f_{j, S \cup \{k\}} \gets f_{i, S}。要求 a_j \ge \frac{b_k}{j - i}。

发现这个 dp 太蠢了。考虑直接把第一维塞进 dp 值中。重新设 f_S 为已经考虑完的集合的编号集合为 S，若 [1, i] 被分配完了，i 的最小值。预处理出 g_{i, j} 表示最小的 k 使得 a_k \ge \frac{b_i}{k - j}，转移考虑枚举下一个集合是第 k 个，有 f_{S \cup \{k\}} \gets g_{k, f_S + 1}。

求 g 可以双指针，因为 g_{i, j} 随 j 增大而不降。所以整个的复杂度就是 O((n + 2^m) m + n \log n)。

code