题解：AT_agc040_d [AGC040D] Balance Beam

Felix72 · 2025-12-05 07:30:17 · 题解

写一个可能是题解区最简单的反悔贪心解法。

考虑有一个“判定点”，我们要求当 \text{Ringo} 从判定点出发时，\text{Snuke} 能够追上他。考虑对于一个固定的判定点检查是否有合法的排列方式。

先考虑判定点在整数位置的情况。则平衡木 i 有三种可能的情况：

• 在判定点左边，则只有 \text{Snuke} 走过去，贡献为 a_i；
• 在判定点右边且 \text{Snuke} 追上 \text{Ringo} 之前两人会走到，贡献为 a_i - b_i；
• 在判定点右边且钦定两人不会走到这里，贡献为 0。

则只要存在一种划分方式使得一类平衡木有 k 个且总贡献不大于 0，则判定点 k 合法。容易使用调整法求解该问题，即先把 a_i \leq b_i 的平衡木划分为第二类，a_i > b_i 的划分为第三类，再反悔 k 次即可。二类的反悔代价是 b_i，三类是 a_i。

现在的问题是判定点可能不在整数位置。我们发现这等价于把一块平衡木“部分反悔”。具体的，我们可以返回一块平衡木的 k \ (0 < k < 1) 部分，若该平衡木为二类，代价是 kb_i，是三类则为 b_i + k(a_i - b_i)（读者自证不难），故我们可以枚举部分反悔哪一块平衡木，剩下的能反悔几块就返回几块，最后算一下这块平衡木的 k 是多少，对所有情况取 \max 即可。