CF2089B1 题解

Pretharp · 2025-03-24 11:34:42 · 题解

先简单说一下题意，给定长度为 n 的序列 a 和 b，一次操作可以让两个序列中的对应位置减去二者较小值（即 a_i \gets a_i - \min\{a_i,b_i\}，b_i 同理），然后将 a 整体循环向右移一位（最后一个数放到序列开头）。问最早多少次操作后 a 中所有数会变为 0，保证 \sum a < \sum b，即答案在有限次操作内。

先手动模拟观察性质。对于 a_{l} 到 a_r，令 s_1 = \sum\limits_{i=l}^r a_i，s_2 = \sum\limits_{i=l}^r b_i，不难发现在 r-l+1 次操作之后，一定有 s_1 \gets s_1 - \min\{s_1,s_2\} 且 s_2 \gets s_2 - \min\{s_1,s_2\}。如果有 s_1 \le s_2，那么在 r-l+1 次操作后 s_1 的值一定为 0。换而言之，a_l 到 a_r 均变为了 0。

所以说对于 a_i，令它最早归 0 的时刻为 t，那么一定有 a_i 到 a_{i+t-1} 这一段数的和小于等于 b_i 到 b_{i+t-1} 的和（为方便表示，此处并不严谨，假设下标从 0 开始，如果下标 x \ge n，则应有 x \gets x \bmod n）。

此时我们只需要对于每一个 a_i 求出它的最早归 0 时刻 t，再将所有 t 取最大值即为答案。这一过程可以用单调栈维护。实现细节参见提交记录。