题解 P2570 [ZJOI2010]贪吃的老鼠

· · 题解

感觉这题非常神仙，题解区几乎没有令人满意的 “差分建图” 正确性的证明，感谢 @p_b_p_b 和 @精神小火 指导。

先用一些套路，我们可以想到二分答案，把蛋糕出现的时间离散化，把老鼠分成若干个不相交的区间。

此时唯一的问题是 怎么解决不能让很多老鼠同时吃一个蛋糕。

首先考虑一个结论 ： 在所有奶酪能被吃的时间相等的情况下，设他们能吃的时间是 time ， 我们把老鼠按速度 v 从大到小排序，奶酪从大到小按 p 排序，那么这些老鼠可以按照题目要求吃掉这些奶酪，当且仅当 \forall i , time (\sum_{j=1} ^i v_j) \geq \sum_{j=1}^i p_j 。

考虑如果这个结论成立，我们该怎么建图， 先把 v 按从大到小排序。

\sum_{j=1}^i v_j=\sum_{j=1}^i \sum_{k=j}^i(v_k-v_{k+1}) = \sum_{k=1}^i (v_k - v_{k+1}) \times k

我们把一个点的意义设置为 v_k-v_{k+1} ，从这个点向每个奶酪连 (v_k-v_{k+1}) \times time ，原点向第 k 个点连 k \times (v_k-v_{k+1}) \times time 。

此时，考虑一种不满足上述结论的奶酪，假设前 t 的时候他不满足，那么在这 t 个的时候，所有点向这前 t 个点的集合连的总流量是 \sum_{i=1}^n (v_{i}-v_{i+1}) \times \min(i,t)=\sum_{i=1}^t v_i ，满足我们的需求。

再来考虑结论的正确性，可能略微有点抽象。

考虑在可以被无线划分的时间轴上一个类似归纳的过程，记 \Delta 为最小的时间单位。

首先明确一个事情，我们可以通过让 v_a 吃 \Delta 的 p_a , 让 v_b 吃 \Delta 的 p_b ，再让 v_a 吃 \Delta 的 p_b , 让 v_b 吃 \Delta 的 p_a ，这样我们达到了一个目的：让两只 \frac{v_a+v_b}{2} 的老鼠吃了 2 \Delta 的 p_a, p_b 。

扩展上述操作，调整 \Delta 的系数，我们就可以做到把老鼠加权平均。

再考虑去归纳，如果 \Delta 之后，所有的老鼠仍然满足条件，那么命题就得证了，下文的 v_i, p_i 都是从大到小排序之后的。

我们只需要让 v_i 吃 p_i \Delta 的时间，然后去加权平均调整这些老鼠，使他仍然满足条件即可， 我们可以按如下方式调整：

把 v_1 和 v_2 加权调整使得恰好满足 v_1 \times left \geq p_1 , left 是剩下的时间。

再把 v_2 和 v_3 加权调整使得恰好满足 v_2 \times left \geq p_2 , left 是剩下的时间。

不断重复上述过程，一定会得到满足。

一种特殊的情况是 v_1,v_2 无论如何加权都大于 p_1 ，我们找到他后面第一个可以加权恰好等于 p_1 的 v_i 然后调整即可。