题目理解（回顾）

我们有：

· 序列 $a_0 \dots a_{n-1}$ 和 $b_0 \dots b_{n-1}$，满足 $\sum a \le \sum b$。 · 初始可做 恰好 $k$ 次 修改：每次选一个 $a_i > 0$ 将其减 1（$k \le \sum a$）。 · 之后进行 若干轮 操作，每轮分为三步：

1. $t_i = \min(a_i, b_i)$，$a_i \leftarrow a_i - t_i$，$b_i \leftarrow b_i - t_i$。
2. $c_i \leftarrow a_{(i-1) \bmod n}$。
3. $a_i \leftarrow c_i$（相当于全体 $a$ 向右循环移动一位）。 · 问：在恰好 $k$ 次修改后，让 $a$ 全为 $0$ 所需的最少轮数。

关键转化

定义： c_i = a_i - b_i

· 初始 $a$ 会先进行 $k$ 次修改（减少某些 $a_i$），然后再执行若干轮操作。 · 一轮操作实际效果： · 先同时做 $a_i \leftarrow a_i - \min(a_i, b_i)$，$b_i$ 也减少同样值。 · 然后 $a$ 整体向右循环一位。

观察：

· 一轮操作后，$b_i$ 变为 $b_i - \min(a_i, b_i)$，相当于 $b_i$ 减少 $\min(a_i, b_i)$。 · 但更关键的是，如果我们定义“净剩余” $d_i = a_i - b_i$，一轮操作后，$d$ 如何变化？

实际上，我们可以将问题看作： 每一轮，$a$ 向右移动一位，同时每个位置上的 $a_i$ 和 $b_i$ 会同时减去 $\min(a_i, b_i)$。 这等价于：$a$ 向右移动，且移动前每个位置上的“多余部分”会被 $b$ 消去。

更清晰的模型

设 $S = \sum a_i$，$T = \sum b_i$。 已知 $S \le T$，$k \le S$。

我们可选的 $k$ 次修改，相当于从 $\sum a$ 中提前扣除 $k$，分配到各个 $a_i$ 上（但不能让 $a_i < 0$）。 修改后的 $a$ 记为 $a'$，满足 $\sum a' = S - k$。

然后进行若干轮操作。 一轮操作实际减少的 $a$ 总量 = $\sum \min(a_i, b_i)$。 因为最终要让 $a$ 全 0，且 $b$ 也会被消耗。

数学等价形式

定义 $c_i = a_i - b_i$（可以为负）。 一轮操作后，$a_i$ 先变成 $\max(a_i - b_i, 0)$，然后整体右移。

设 $x$ 为轮数。 经过 $x$ 轮后，每个位置 $i$ 的最终 $a$ 值，等于初始 $a$ 中某个区间（长度为 $x$ 的窗口）内的“剩余”的累计。

实际上，本题的标程采用了一种二分 + 单调栈的方法，直接计算在 $x$ 轮内是否能使 $a$ 归零。

标程算法解释

第一步：预处理

· 读入 $n, k$ 和数组 $a, b$。 · 计算 $suma = \sum a_i$。 · 如果 $suma = k$，说明修改后 $a$ 已全 0，输出 0。 · 否则，定义新数组 $a'_i = a_i - b_i$（允许负数），然后复制一份接到后面：$a'_{i+n} = a'_i$（长度 $2n$）。 · 计算前缀和 $a'$（注意：代码中 a[i] 实际存的是 $a_i - b_i$ 的前缀和）。

为什么？ 因为一轮操作中，$a$ 向右移，相当于我们每次取一个长度为 $x$ 的窗口，窗口内的 $a_i - b_i$ 之和必须 ≤ 0（否则消不完）。

第二步：找起始位置

· 在 $[n, 2n-1]$ 范围内，找前缀和最小的位置 pos。 这样能保证从该位置开始，后面的 $n$ 个前缀和不会突然变大，便于处理。

第三步：二分轮数 $x$

· 二分答案 $x$（$1 \le x \le n$），判断是否能在 $x$ 轮内清空 $a$。 · 判断函数 judge(x)： · 用单调栈维护一个递减的 $a'_i$ 值。 · 从 pos 往左遍历（长度为 $n$ 的区间），计算需要的修改次数。 · 修改次数 = 当前值减去栈顶值的正部分，累加。 · 若累加 > $k$，则 $x$ 不可行。

为什么这样正确？ 因为 $x$ 轮相当于我们要覆盖每个位置上的“缺口”，而单调栈帮助我们找到当前窗口内的最小值，从而计算必须提前修改的量。

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll t, n, k, pos;
ll a[400009], stk[400009];

inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch <= '9' && ch >= '0') {
        s = (s << 1) + (s << 3) + (ch ^ 48);
        ch = getchar();
    }
    return s * w;
}

bool judge(ll x) {
    ll l = 1, r = 0, res = 0;
    for (ll i = pos; i >= pos - n; i--) {
        if (l <= r && stk[l] - i > x) l++;
        if (pos - i >= x) res += max(0ll, a[stk[l]] - a[i]);
        if (res > k) return false;
        while (l <= r && a[stk[r]] > a[i]) r--;
        stk[++r] = i;
    }
    return true;
}

int main() {
    t = read();
    while (t--) {
        n = read(); k = read();
        ll suma = 0;
        for (ll i = 1; i <= n; i++) {
            a[i] = read();
            suma += a[i];
        }
        for (ll i = 1; i <= n; i++) {
            ll b = read();
            a[i] -= b;
            a[i + n] = a[i];
        }
        if (suma == k) {
            puts("0");
            continue;
        }
        for (ll i = 1; i <= 2 * n; i++) a[i] += a[i - 1];
        
        pos = n;
        for (ll i = n + 1; i <= 2 * n; i++) {
            if (a[i] < a[pos]) pos = i;
        }
        
        ll l = 1, r = n, ans = n;
        while (l <= r) {
            ll mid = (l + r) >> 1;
            if (judge(mid)) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

时间复杂度

· 对每个测试用例：二分 $O(\log n)$ 次，每次 judge 是 $O(n)$，单调栈维护 $O(n)$。 · 总复杂度 $O(\sum n \log n)$，满足 $2 \cdot 10^5$ 的数据范围。

总结

本题的核心是：

1. 将问题转化为在长度为 $n$ 的环上，用 $x$ 轮操作清空 $a$。
2. 利用 $c_i = a_i - b_i$ 的前缀和与单调栈，判断最少需要的提前修改次数。
3. 二分答案 $x$，找到最小可行轮数。