【GESP】C++六级/五级练习题 luogu-P2629 好消息，坏消息
GESP C++ 六级/五级练习题，前缀和思想和队列数据结构考点应用，五六级考生均可以练习。题目难度⭐⭐⭐☆☆，洛谷难度等级普及/提高−。
luogu-P2629 好消息，坏消息
题目要求
题目描述
Uim 在公司里面当秘书，现在有 $n$ 条消息要告知老板。每条消息有一个好坏度，这会影响老板的心情。告知完一条消息后，老板的心情等于老板之前的心情加上这条消息的好坏度。最开始老板的心情是 $0$，一旦老板心情到了 $0$ 以下就会勃然大怒，炒了 Uim 的鱿鱼。
Uim 为了不被炒，提前知道了这些消息（已经按时间的发生顺序进行了排列）的好坏度，希望知道如何才能不让老板发怒。
Uim 可以使用一种叫 “倒叙” 的手法，例如有 $n$ 条消息，Uim 可以任取一个整数 $k$（$1 \leq k \leq n$），先从 $k$ 事件通报到 $n$ 事件，再从 $1$ 事件通报到 $k-1$ 事件。特别的，当 $k=1$ 时按照原顺序通报。
他希望知道，有多少个这样的 $k$ 可以让老板不发怒。
输入格式
第一行一个整数 $n$（$1 \le n \le10^6$），表示有 $n$ 个消息。
第二行 $n$ 个整数，按时间顺序给出第 $i$ 条消息的好坏度 $A_i$（$-10^3\le A_i \le 10^3$）。
输出格式
一行一个整数，表示可行的方案个数。
输入输出样例 #1
输入 #1
1
2
4
-3 5 1 2
输出 #1
1
2
说明/提示
【样例解释】
通报事件的可行顺序（用编号表示）为 $2\rightarrow3\rightarrow4\rightarrow1$ 或 $3\rightarrow4\rightarrow1\rightarrow2$（分别对应 $k=2$ 和 $k=3$）
通报事件的可行顺序（用好坏度表示）为 $5\rightarrow1\rightarrow2\rightarrow(-3)$ 或 $1\rightarrow2\rightarrow(-3)\rightarrow5$
【数据范围】
对于 $25\%$ 的数据，$n\le10^3$；
对于 $75\%$ 的数据，$n\le10^4$；
对于 $100\%$ 的数据，$1 \le n\le 10^6$。
题目分析
这道题目要求我们在一个环形序列中找到合适的起始位置 $k$，使得从 $k$ 开始遍历一圈的过程中，累加和始终保持非负。
1. 断环成链
处理环形问题的一个常用技巧是“断环成链”。 原序列是 $A_1, A_2, \dots, A_n$。 我们将原序列复制一份接在末尾，形成长度为 $2n$ 的新序列：$A_1, A_2, \dots, A_n, A_1, A_2, \dots, A_n$。 这样，原序列中任意一种“倒叙”手法（即从 $k$ 开始的循环移位），都对应新序列中一段长度为 $n$ 的连续子区间 $[k, k+n-1]$。
2. 前缀和
为了快速计算区间和，我们需要使用前缀和。 设 pre[i] 表示新序列前 $i$ 项的和，即 pre[i] = A[1] + ... + A[i]。 那么子区间 $[k, j]$ 的和可以表示为 pre[j] - pre[k-1]。
题目要求老板的心情始终不能小于 0。 这意味着，对于确定的起始位置 $k$，在区间 $[k, k+n-1]$ 内的任意位置 $j$ ($k \le j \le k+n-1$)，都要满足： \(\text{当前心情} = \text{pre}[j] - \text{pre}[k-1] \ge 0\) 即： \(\text{pre}[j] \ge \text{pre}[k-1]\)
要让上述不等式对区间内所有的 $j$ 都成立，只需让区间内的最小值满足即可： \(\min_{k \le j \le k+n-1} \{ \text{pre}[j] \} \ge \text{pre}[k-1]\)
3. 单调队列优化
现在问题转化成了：对于每一个可能的起点 $k$ ($1 \le k \le n$)，我们需要查询长度为 $n$ 的区间 $[k, k+n-1]$ 内 pre 数组的最小值。 这是一个典型的滑动窗口最小值问题。
如果我们暴力遍历寻找最小值，总时间复杂度是 $O(n^2)$。考虑到 $n \le 10^6$，这会超时。 我们可以使用单调队列（双端队列 std::deque）来优化，将时间复杂度降低到 $O(n)$。
- 维护单调递增队列：队列中存储数组下标，对应的
pre值单调递增。 - 入队：当遍历到一个新元素
pre[i]时，如果它比队尾元素对应的pre值小（或相等），说明队尾元素不可能是未来的最小值了（因为pre[i]更小且更靠后），将队尾元素弹出。然后将 $i$ 入队。 - 出队（滑出窗口）：如果队头元素对应的下标已经滑出了当前窗口范围（即下标 $< k$），则将队头弹出。
- 查询：队头元素对应的
pre值即为当前窗口的最小值。
总结
- 读取输入 $n$ 和数组 $A$，并将 $A$ 复制一份接在后面。
- 计算前缀和数组
pre。 - 利用单调队列维护长度为 $n$ 的滑动窗口内的
pre最小值。 - 枚举起点 $k$ 从 $1$ 到 $n$，判断窗口最小值是否大于等于
pre[k-1]，统计符合条件的 $k$ 的个数。
时间复杂度：$O(n)$。 空间复杂度：$O(n)$。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <deque>
#include <iostream>
// 数组大小设置为 2*10^6，因为 n 最大为 10^6，且需要断环成链开两倍空间
int a[2000005];
int pre[2000005]; // 前缀和数组
int main() {
int n;
std::cin >> n;
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
// 断环成链：将原数组复制一份接在后面，模拟环状结构
// 这样处理后，从任意 k 开始的长度为 n 的序列在数组中就是连续的一段
a[i + n] = a[i];
}
// 计算前缀和
// pre[i] 表示序列前 i 项的和。
// 注意这里计算到了 2*n - 1，覆盖了所有可能的起始位置延展出的 n 长度序列
for (int i = 1; i < 2 * n; i++) {
pre[i] = pre[i - 1] + a[i];
}
int count = 0;
std::deque<int> q; // 单调队列，用于维护当前滑动窗口内的最小前缀和的下标
// 遍历所有可能的结束位置 i
for (int i = 1; i < 2 * n; i++) {
// 维护单调递增队列：
// 如果新元素 pre[i] 比队尾元素更小（或相等），
// 那么队尾元素就不可能是当前或未来窗口的最小值了，可以直接弹出
while (!q.empty() && pre[q.back()] >= pre[i]) {
q.pop_back();
}
q.push_back(i);
// 如果 i >= n，说明窗口大小已经达到了 n，可以开始判断是否有解
// 此时窗口对应的原序列起始位置 k = i - n + 1
if (i >= n) {
int k = i - n + 1;
// 检查队头元素是否已滑出窗口 [k, i]
// 如果队头下标小于 k，说明该最小值不在当前考虑的区间内，弹出
if (!q.empty() && q.front() < k) {
q.pop_front();
}
// 我们只关心 k 在 1 到 n 之间的情况
if (k <= n) {
// 核心判断逻辑：
// 如果从 k 开始每一步累加都不小于 0，等价于
// 区间 [k, k+n-1] 内的所有前缀和 pre[j] 减去 pre[k-1] 都 >= 0
// 即：min(pre[k...i]) - pre[k-1] >= 0
// q.front() 保存了区间 [k, i] 内最小前缀和的下标
if (pre[q.front()] - pre[k - 1] >= 0) {
count++;
}
}
}
}
std::cout << count;
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
