挑战 NPC 最后更新于 2025-05-01 20:57:46

赛时做法，但是挂成6分了捏。 首先二分答案。 设第 $i$ 小组共分到 $v_i$ 个，第 $i$ 小组一共有 $c_i$ 个人。 实际上是在判断是否存在一组 $v$ 满足如下条件： 1.$\max v_i- \min v_i \le d$ 2.$\max \lceil\frac{v_i}{c_i}\rceil - \min \lfloor\frac{v_i}{c_i}\rfloor \le d$ 3.$\sum v_i = m$ 考虑先枚举 $\min \lfloor\frac{v_i}{c_i}\rfloor$。 于是每一个 $v_i$ 会有一个区间的限制 $[l_i,r_i]$，对 $c_i$ 排序则 $l_i ,r_i$ 均单调递增。 再枚举 $t=\min v_i$ ，于是相当于对每个区间变为 $[\max(l_i,t),\min(r_i,t+d)]$。 此时第三个条件等价于: 1.$ \sum \max(l_i,t) \le m \le \sum \min(r_i,t+d)$ 2.$ \max(l_i,t) \le \min(r_i,t+d) $ 对每个 $i$ 满足第2个条件的 $t$ 是一段区间，事先求出后直接枚举判断第一个条件，此时只需二分出 $l_i \le t$ 的 $i$ 计算两个部分的和，$r$ 的部分同理。 不过因为此时处理了第二个条件所以 $l,r$ 独立了。所以分开考虑 $\sum \max(l_i,t) \le m$ 以及 $m \le \sum \min(r_i,t+d)$ 即可。 不难发现对于 $l$ 的限制满足条件的是一段前缀。对 $r$ 的限制满足条件的是一段后缀。只需对 $l$ 二分出最后一个满足条件的位置 $p1$,对 $r$ 二分出最后一个满足条件的位置 $p2$，判断 $p1$ 是否大于等于 $p2$ ，这样我们就只需枚举 $\min \lfloor\frac{v_i}{c_i}\rfloor$。 这时你发现满足条件的 $\min \lfloor\frac{v_i}{c_i}\rfloor$ 是一段区间，但是不是前缀和后缀。设 $f_{x}$ 表示 $\min \lfloor\frac{v_i}{c_i}\rfloor=x$ 时的 $p1-p2$，发现这是一个单峰函数，可以直接三分出最大值！ 因为知道了答案，$\min \lfloor\frac{v_i}{c_i}\rfloor$ 还有 $t$，构造方案是简单的。复杂度 $O(n \log^2 m + \log^3 m \log n)$。 虽然 $n$ 看上去很大，但是因为对 $c_i$ 相同的 $i$ 它的 $l_i,r_i$ 都相同，所以实际上只需对本质不同的 $c_i$ 计算，又因为 $\sum c_i \le 10^9$ 所以 $n$ 是可以和 $\sqrt {10^9}$ 取 $\min $ 的。