自动搬运

查看原文

来自洛谷，原作者为

	zhouyuhang Bénédiction de Dieu dans la solitude

搬运于2025-08-24 22:58:54，当前版本为作者最后更新于2024-05-25 22:17:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

vp 的时候没来及看这题，后来想了想会了。题解区另一篇题解不知道在干什么，所以下面是一个非常简单的做法。

首先将路程划分为 $0 \to x_1, x_1 \to x_2, \cdots, x_n \to 0$ 这 $n + 1$ 个部分，并记第 $i$ 个部分 $y$ 坐标的变化量为 $y_i$，定义第 $i$ 段的代价函数 $f_i(y) = \left(M + \sum _ {j = i} ^ n m_j \right) \sqrt {d_i ^ 2 + y ^ 2}$，其中 $d_i = |x_i - x_{i - 1}|$，$x_0 = x_{n + 1} = 0$，则题目即要求我们在 $\sum _ {i = 1} ^ {n + 1} y_i = y$ 的条件下最小化 $\sum _ {i = 1} ^ {n + 1} f_i(y_i)$ 的值。

而这是简单的，只需注意到在最优方案中一定有 $f_1'(y_1) = f_2'(y_2) = \cdots = f_{n + 1}' (y_{n + 1})$，否则对于 $f_i'(y_i) < f_j'(y_j)$，我们只需将 $y_i$ 调小 $y_j$ 调大即可获得一组更优解。而注意到 $f_i'(y) = \left(M + \sum _ {j = i} ^ n m_j \right) \frac {y} {\sqrt{d_i ^ 2 + y ^ 2}}$ 单增，因此我们直接二分导函数的值并回代即可做到 $O(n \log V)$。