自动搬运

查看原文

来自洛谷，原作者为

	zhouyuhang Bénédiction de Dieu dans la solitude

搬运于2025-08-24 23:03:53，当前版本为作者最后更新于2024-08-09 00:01:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

记第 $i$ 个香蕉参与合并的次数为 $c_i$，我们所需做的就是最大化 $\sum _ {i = 1} ^ n a_i k_i ^ {-c_i}$。

Hint：最优的合并策略中，必然有 $\{c_1, c_2, \cdots, c_n\} = \{1, 2, 3, \cdots, n - 1, n - 1\}$。

证明：使用调整法。考虑合并形成的最优二叉树，设其不满足上述性质，则必然存在至少两个节点，满足其两个儿子均为叶子节点。则这样的节点中深度次深的 $x$，记其两个儿子为 $a, b$；再取与 $x$ 同深度的另一节点 $y$，记其两个儿子为 $c, d$。由于 $x$ 是次深的，因此 $y$ 必然存在，且 $c, d$ 中至少有一个是叶子节点，不妨设其为 $c$。

接下来，记 $v_x = a_x k_x ^ {-c_x}$，则在原树中，$a, b, c$ 三点对答案的贡献即为 $v_a + v_b + v_c$。注意到，这里的 $a, b, c$ 可以随意进行调换，因此我们不妨设 $(1 - \frac 1 {k_c}) v_c \ge \max((1 - \frac 1 {k_a}) v_a, (1 - \frac 1 {k_b}) v_b)$ 最大。我们作形如这样的调整：将 $d$ 的整个子树插入到上方，使其成为 $x$ 的兄弟。注意到，此时 $d$ 子树的深度完全没有发生变化，而 $c$ 的深度减少 $1$，$a, b$ 的深度增加 $1$，从而 $a, b, c$ 对答案的贡献变为 $\frac {v_a} {k_a} + \frac {v_b}{k_b} + v_ck_c$。与原来的贡献相减，得到 $\Delta = (k_c - 1)v_c - ((1 - \frac 1 {k_a}) v_a + (1 - \frac 1 {k_b}) v_b)$。而注意到 $(k_c - 1)v_c = k_c (1 - \frac 1 {k_c})v_c \ge 2 (1 - \frac 1 {k_c})v_c \ge (1 - \frac 1 {k_a}) v_a + (1 - \frac 1 {k_b}) v_b$，也即 $\Delta \ge 0$。因此，这样的调整总会让答案不劣。同时，注意到每次调整后，所有叶子节点的深度和总会 $+1$，这说明我们的调整过程是单调的，最终总能使其到达 Hint 中所描述的状态。故证毕。

回到原题，现在我们已经知道可重集 $\{c_1, c_2, \cdots, c_n\}$，我们只需对每个 $i$ 分配对应的 $c_i$。如果暴力进行二分图最大权匹配，未免代价有些太过高昂。注意到，当 $c_i \ge 50$ 时，有 $n a_i k_i ^ {- c_i} \le 10 ^ 5 \cdot 10 ^ 5 \cdot 2 ^ {-50} < \epsilon = 10 ^ {-5}$，因此我们只需保留右部的 $O(\log V)$ 个点。进一步的，我们发现在 $k_i$ 相同时，$a_i$ 较大的点被分配到的 $c_i$ 一定较小，因此我们对于同一个 $k_i$ 也只需保留前 $50$ 大的 $a_i$。这样左部点的数量也被压缩到了 $O(k \log V)$。而在这张图上跑费用流的复杂度即为 $O(k\log V \cdot k \log ^ 2 V \cdot \log V) = O(k ^ 2 \log ^ 4 V)$，足以通过。