自动搬运

查看原文

来自洛谷，原作者为

	YksKuusiTAlv 「誰であれ、光の前に立つ者には――必ず影ができる。」

搬运于2025-08-24 21:39:11，当前版本为作者最后更新于2022-06-26 17:58:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 这是我最后一次交题解，交题解纯属因为题解区根本没有正确的证明，实在是懒得改什么 Latex 了，爱过不过吧。

感觉这题非常神仙，题解区几乎没有令人满意的 “差分建图” 正确性的证明，感谢 @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$ 然后调整即可。