B1. Canteen (Easy Version) 详细题解

题目描述

这是该问题的简单版本，其中 $k = 0$，即不能对序列 $a$ 做任何修改。

给定两个长度为 $n$ 的整数序列 $a_0, a_1, \dots, a_{n-1}$ 和 $b_0, b_1, \dots, b_{n-1}$，保证 $\sum a_i \le \sum b_i$。

每轮操作分为三步：

1. 消耗阶段：对于每个 $i$，令 $t = \min(a_i, b_i)$，然后：$$a_i := a_i - t,\quad b_i := b_i - t$$
2. 移位阶段：将 $a$ 数组循环右移一位，即：$$c_i := a_{(i-1) \bmod n},\quad a_i := c_i$$
3. 重复上述过程直到所有 $a_i = 0$

求最少需要的轮数。

---

核心思想

1. 问题转化

对于每个位置 $i$ 上的初始 $a_i$，它会在若干轮后被消耗完。由于 $a$ 每轮向右循环移位，第 $i$ 个位置的 $a_i$ 实际上会依次与 $b_i, b_{i+1}, b_{i+2}, \dots$ 进行匹配（下标模 $n$）。

定义 $d_i$ 为将 $a_i$ 减少到 $0$ 所需的最小轮数，那么答案就是：

$$\text{ans} = \max_{0 \le i < n} d_i$$

2. 循环展开

对于循环问题，将数组复制一份接在后面：

$$a_{i+n} = a_i,\quad b_{i+n} = b_i$$

这样只需要考虑长度为 $2n$ 的链，$d_i$ 就是找到最小的 $j \ge i$ 使得 $a_i$ 可以被 $b_i, b_{i+1}, \dots, b_j$ 完全消耗。

3. 括号匹配模型

构造一个括号序列：将每个 $a_i$ 视为 $a_i$ 个左括号 (，每个 $b_i$ 视为 $b_i$ 个右括号 )，按顺序拼接：

$$s = \underbrace{(\cdots(}_{a_0\text{个}} \underbrace{)\cdots)}_{b_0\text{个}} \underbrace{(\cdots(}_{a_1\text{个}} \underbrace{)\cdots)}_{b_1\text{个}} \cdots \underbrace{(\cdots(}_{a_{2n-1}\text{个}} \underbrace{)\cdots)}_{b_{2n-1}\text{个}} $$

原问题的操作对应括号匹配过程：

• 第一步（$\min(a_i, b_i)$ 归零）对应将当前位置的左右括号进行匹配消除
• 第二步（$a$ 循环右移）对应未匹配的左括号继续向右寻找右括号

因此，$a_i$ 第一次被归零的时刻，取决于 $a_i$ 对应的左括号与哪个 $b_j$ 的右括号完成匹配。

4. 前缀和与单调栈

定义差分：

$$d_i = a_i - b_i$$

计算前缀和：

$$c_i = \sum_{j=0}^{i} (a_j - b_j) = \sum_{j=0}^{i} d_j,\quad 0 \le i < 2n $$

括号匹配的关键观察：
对于位置 $i$，$a_i$ 对应的左括号找到匹配右括号的位置 $p_i$ 是满足 $p_i > i$ 且 $c_{p_i} \le c_i$ 的最小下标。

原因：

• $c_i$ 表示到位置 $i$ 为止未匹配的左括号数量（左括号为正，右括号为负）
• 当 $c$ 的值下降到不高于 $c_i$ 时，意味着 $i$ 之后出现的左括号已经全部被匹配，$i$ 处的左括号也得到了匹配
• $p_i$ 就是 $a_i$ 被完全消耗时对应的 $b$ 的位置

于是：

$$d_i = p_i - i$$

5. 单调栈求 $p_i$

需要找到每个 $i$ 右边第一个满足 $c_j \le c_i$ 的位置 $j$，使用单调递增栈（按 $c$ 值）从右向左扫描：

• 初始化空栈，答案 $ans = 0$
• 从 $i = 2n-1$ 向下遍历到 $0$：
  • 当栈非空且 $c[\text{栈顶}] > c[i]$ 时，弹出栈顶（维护单调递增）
  • 此时栈顶就是右边第一个 $c$ 值不大于 $c[i]$ 的位置，即 $p_i$（若栈空则 $p_i = 2n$）
  • 如果 $i < n$，则 $ans = \max(ans, \text{栈顶} - i)$
  • 将 $i$ 入栈

---

算法步骤

1. 读入 $n, k$（$k=0$ 不影响）
2. 读入数组 $a[0..n-1]$ 和 $b[0..n-1]$
3. 构造长度为 $2n$ 的差分数组并计算前缀和 $c$
4. 使用单调栈从右向左扫描，计算每个 $i$ 对应的 $p_i - i$，更新答案
5. 输出答案

---

时间复杂度

• 每个测试用例 $O(n)$
• 所有测试用例的 $n$ 总和不超过 $2 \times 10^5$，完全可行

---

代码实现（C++）

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

const int MAXN = 400009;
ll n, k;
ll a[MAXN], stk[MAXN];

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;
}

int main() {
    ll t = read();
    while (t--) {
        n = read(), k = read();  // k = 0 in this version
        
        // 读入 a 数组
        for (ll i = 1; i <= n; i++) {
            a[i] = read();
        }
        
        // 计算 a[i] - b[i]，并复制一份
        for (ll i = 1; i <= n; i++) {
            ll b = read();
            a[i] = a[i + n] = a[i] - b;
        }
        
        // 计算前缀和
        for (ll i = 1; i <= 2 * n; i++) {
            a[i] += a[i - 1];
        }
        
        // 单调栈从右向左扫描
        ll tp = 0, ans = 0;
        for (ll i = 2 * n; i >= 1; i--) {
            // 维护单调递增栈（按 a[栈顶] 的值）
            while (tp && a[stk[tp]] > a[i]) {
                tp--;
            }
            // 对于原始范围内的位置，更新答案
            if (i <= n) {
                ans = max(ans, stk[tp] - i);
            }
            // 当前下标入栈
            stk[++tp] = i;
        }
        
        printf("%lld\n", ans);
    }
    return 0;
}

---

示例验证

示例输入

4
3 0
1 1 4
5 1 4
4 0
1 2 3 4
4 3 2 1
4 0
2 1 1 2
1 2 2 1
8 0
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1

示例输出

1
4
4
8

第一个测试用例详解

$n=3,\ a=[1,1,4],\ b=[5,1,4]$

计算 $d = a-b = [-4, 0, 0]$，复制得 $d = [-4,0,0,-4,0,0]$

前缀和 $c$：

$$c_1=-4,\ c_2=-4,\ c_3=-4,\ c_4=-8,\ c_5=-8,\ c_6=-8 $$

从右向左单调栈扫描：

• $i=6$：栈空，入栈 → 栈 $=[6]$，$i>n$ 不更新
• $i=5$：$c_5=-8 \le c_6=-8$，不弹出，入栈 → 栈 $=[6,5]$
• $i=4$：$c_4=-8 \le c_5=-8$，不弹出，入栈 → 栈 $=[6,5,4]$
• $i=3$：$c_3=-4 > c_4=-8$，弹出 4；$-4 > c_5=-8$，弹出 5；$-4 > c_6=-8$，弹出 6；栈空，$p_3$ 不存在，取 $p_3=7$，$d_3=4$
• $i=2$：$c_2=-4 > c_3=-8$，栈空，$d_2=5$
• $i=1$：$c_1=-4$，栈空，$d_1=6$

但实际模拟可知答案应为 1，说明上述计算有误。注意：题目保证 $\sum a \le \sum b$，但前缀和 $c_i$ 可能在末尾大于起点，需要特殊处理。实际标程中，由于栈中始终有元素（复制保证了末尾有更小值），栈不会为空。正确的单调栈维护的是严格大于才弹出，保证栈底是全局最小值。

重新计算正确过程：

• $i=6$：栈 $=[6]$
• $i=5$：$c_5=-8 \le c_6=-8$，不弹出，栈 $=[6,5]$
• $i=4$：$c_4=-8 \le c_5=-8$，不弹出，栈 $=[6,5,4]$
• $i=3$：$c_3=-4 > c_4=-8$，弹出 4，栈 $=[6,5]$；$-4 > c_5=-8$，弹出 5，栈 $=[6]$；$-4 \le c_6=-8$？实际 $-4 > -8$，继续弹出 6，栈空。此时 $i=3$ 栈空，取 $p_3=7$，$d_3=4$，但答案应为 1，说明此处 $i=3$ 不在 $[1,n]$ 范围内（$i=3>n=3$？注意下标从 1 开始，$i=3$ 对应原始位置 2，实际上 $i=3$ 是 $n=3$ 的边界，应计入）。需要仔细核对。

实际上，对于 $i=2$（原始位置 1）：$c_2=-4$，右边第一个 $c_j \le -4$ 且 $j>2$ 的是 $j=3$（$c_3=-4$），$d_2=1$。对于 $i=1$（原始位置 0）：$c_1=-4$，右边第一个 $c_j \le -4$ 的是 $j=2$，$d_1=1$。最大值确实为 1。

---

总结

本题的核心是将原问题映射到括号匹配模型，通过构造括号序列并利用前缀和与单调栈，在 $O(n)$ 时间内求出每个 $a_i$ 被消耗所需的轮数，取最大值即为答案。这种转化思想在处理循环序列问题时非常有用。