题解：P10529 [XJTUPC2024] 勘探队

zhouyuhang · 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)。