题解 P2629 【好消息，坏消息】(断环成链 + 单调队列)

1. 题目简述

Uim 有 $n$ 条消息，每条消息有一个好坏度 $A_i$ 。老板的心情初始为 $0$ ，依次听完消息后心情会累加。如果过程中老板的心情一旦小于 $0$ ，Uim 就会被炒鱿鱼。 Uim 可以选择从第 $k$ 条消息开始汇报（ $1 \le k \le n$ ），顺序为 $k, k+1, \dots, n, 1, \dots, k-1$ 。问有多少个 $k$ 可以保证汇报过程中老板的心情始终 $\ge 0$ 。

数据范围： $n \le 10^6$ ， $-10^3 \le A_i \le 10^3$ 。

2. 思路分析

难点一：环形处理（断环成链）

题目中可以选择任意起点 $k$ 绕一圈，这是一种典型的环形问题。处理环形问题最常用的技巧是 断环成链：将原数组 $A$ 复制一份接在后面，形成一个长度为 $2n$ 的新数组。

A' = \{A_1, A_2, \dots, A_n, A_1, A_2, \dots, A_{n-1}\}

这样，原数组中从

k

开始长度为

n

的环形序列，就对应新数组中下标

[k, k+n-1]

的连续子段。

难点二：转化条件（前缀和）

设 $S$ 为 $A'$ 的前缀和数组，即 $S_i = \sum_{j=1}^i A'_j$ 。对于一个起始位置 $k$ （在 $A'$ 中对应区间 $[k, k+n-1]$ ），要保证过程中心情始终 $\ge 0$ ，意味着对于区间内任意位置 $j$ ( $k \le j \le k+n-1$ )，都要满足：

区间和(k, j) \ge 0

用前缀和表示就是：

S_j - S_{k-1} \ge 0 \implies S_j \ge S_{k-1}

这个条件必须对区间内所有的

j

都成立。显然，如果区间内最小的那个

S_j

都满足条件，其他肯定也满足。所以条件转化为：

\min_{k \le j \le k+n-1} \{S_j\} \ge S_{k-1}

难点三：滑动窗口最小值（单调队列）

我们需要枚举每一个可能的 $k$ ( $1 \le k \le n$ )。对于每一个 $k$ ，我们需要查询区间 $[k, k+n-1]$ 内 $S$ 的最小值。随着 $k$ 的增加，这个长度为 $n$ 的区间在不断向右滑动。

这正是 单调队列（滑动窗口最小值） 的标准模型！

算法流程：

构造长度为 $2n$ 的数组，计算前缀和 $S$ 。
使用一个单调递增的队列（存下标），维护当前窗口内的 $S$ 值。
遍历 $i$ 从 $1$ 到 $2n-1$ ：
- 入队：如果 $S[i]$ 比队尾小，队尾就没用了，弹出（维护单调性）。
- 出队：如果队头下标 $pos < i - n + 1$ ，说明滑出窗口了，弹出。
- 判断：当 $i \ge n$ 时，说明窗口长度已达到 $n$ 。此时对应的起点是 $k = i - n + 1$ 。检查队头（即窗口内最小值）：如果 $S[q.front()] \ge S[k-1]$ ，则该起点 $k$ 合法，答案 $+1$ 。

时间复杂度： $O(N)$ 。

3. 样例推演

输入：4，数组：-3 5 1 2 断环成链后的数组：-3 5 1 2 -3 5 1 2 前缀和 $S$ (从下标1开始): -3, 2, 3, 5, 2, 7, 8, 10，且 $S[0]=0$ 。

我们需要滑动窗口大小为 4。

i	当前 S[i]	队列状态 (存下标)	窗口范围 (对应起点 k)	窗口最小值 (S[head])	基准值 S[k-1]	判断 S[head] >= S[k-1]
1	-3	`{1}`	-	-	-	-
2	2	`{1, 2}`	-	-	-	-
3	3	`{1, 2, 3}`	-	-	-	-
4	5	`{1, 2, 3, 4}`	$[1, 4] \to k=1$	$S[1] = -3$	$S[0]=0$	$-3 < 0$ (❌)
5	2	队列调整: 2<5(弹4), 2<3(弹3), 2<2(不弹) $\to$ `{1, 2, 5}` 队头1过期(1 < 5-4+1=2) $\to$ `{2, 5}`	$[2, 5] \to k=2$	$S[2] = 2$	$S[1]=-3$	$2 \ge -3$ (✅)
6	7	`{2, 5, 6}`	$[3, 6] \to k=3$	$S[2] = 2$	$S[2]=2$	$2 \ge 2$ (✅)
7	8	`{2, 5, 6, 7}` 队头2过期 $\to$ `{5, 6, 7}`	$[4, 7] \to k=4$	$S[5] = 2$	$S[3]=3$	$2 < 3$ (❌)

统计 ✅ 数量：2。输出 2。

4. AC 代码

cpp

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

// 数据范围 N <= 10^6，开大一点
const int MAXN = 2000005; 
int a[MAXN];
long long s[MAXN]; // 前缀和用 long long 防止溢出（虽然这题int大概率够用）

int main() {
    // 开启 IO 加速
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    if (!(cin >> n)) return 0;

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        // 断环成链：复制一份到后面
        a[i + n] = a[i];
    }

    // 计算前缀和，计算范围到 2*n - 1 即可覆盖所有可能的长度为 n 的窗口
    s[0] = 0;
    for (int i = 1; i < 2 * n; ++i) {
        s[i] = s[i - 1] + a[i];
    }

    deque<int> q;
    int ans = 0;

    // 遍历前缀和数组
    for (int i = 1; i < 2 * n; ++i) {
        // 1. 维护单调递增队列 (找最小值)
        // 如果当前 s[i] 比队尾小，队尾显然不是最小值的候选了
        while (!q.empty() && s[q.back()] >= s[i]) {
            q.pop_back();
        }
        q.push_back(i);

        // 2. 窗口形成判断 (i >= n)
        if (i >= n) {
            // 当前窗口对应的起始位置 k
            // 窗口范围是 [i - n + 1, i]
            int k = i - n + 1;

            // 3. 移除过期元素
            // 如果队头下标小于窗口左边界，弹出
            if (!q.empty() && q.front() < k) {
                q.pop_front();
            }

            // 4. 判断条件
            // 区间内最小的前缀和必须 >= 之前的基准前缀和 s[k-1]
            if (s[q.front()] - s[k - 1] >= 0) {
                ans++;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

5. 总结

断环成链：解决循环数组问题的首选方法。
问题转化：将“全程非负”转化为“区间内最小前缀和 $\ge$ 初始前缀和”。
单调队列：在 $O(N)$ 时间内解决滑动窗口最值问题。
注意细节： $S[i]$ 的计算范围，以及 $k$ 与 $i$ 的下标对应关系。

好消息，坏消息

目录