CF2089B1 题解

先简单说一下题意，给定长度为 $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$ 取最大值即为答案。这一过程可以用单调栈维护。实现细节参见提交记录。