P2629 好消息坏消息 题解复盘基本信息项目内容题目编号、来源P2629 洛谷 / 【LGR-016】洛谷11月月赛·Day2训练层级B 前缀和 单调队列知识版块前缀和、单调队列、环形数组解题前・关键信号识别维度分析目标、约束、底层结构目标找到一个环形起点使得从该点开始按顺序累加过程中前缀和始终 ≥ 0求合法起点个数约束n ≤ 1e6必须 O(n)底层结构断环成链 前缀和 滑动窗口最小值。数据规模n ≤ 1e6O(n log n) 可能卡常O(n) 最优。候选算法和依据前缀和 单调队列依据从起点 k 开始到 kn-1 的累加过程始终 ≥ 0等价于该区间内所有前缀和的最小值 ≥ 起点前的前缀和。复杂度预判时间复杂度 O(n)每个元素入队出队一次空间复杂度 O(n)。解题后・外化复盘维度内容实现结构 / 核心思路第一步将数组复制一份拼接成 2n计算前缀和 s[0…2n]第二步用单调队列维护长度为 n 的窗口内前缀和的最小值第三步枚举起点 i1≤i≤n若窗口 [i, in-1] 内的最小前缀和 ≥ s[i-1]则说明从 i 开始老板全程不生气答案。核心思想环形 → 断环成链全程 ≥ 0 → 前缀和最小值 ≥ 起点前前缀和。错因回溯1. 前缀和只算到 n后面循环访问 s[i] 时全是 0导致答案错误2. 统计答案时范围写成i 2*n导致多统计了不存在的起点正确做法是只统计start n3. 判断条件写成s[start]正确应该是s[start-1]。边界和易错点1. 枚举起点 i 从 1 到 n注意start n才统计2. 前缀和数组开 2n5算到 2n3. 窗口内最小值 ≥ s[start-1] 表示全程累加 ≥ 04. 用数组模拟 deque 提高效率n1e6 时 deque 可能 TLE5. 当 n1 时直接判断 a[1] 0 即可。下次看到什么信号我应该想到这个方法看到「环形数组 累加过程始终 ≥ 0 求合法起点个数」用断环成链 前缀和 滑动窗口最小值。AC 完整代码#includeiostream#includealgorithm#includeset#includequeue#includevectorusingnamespacestd;constintN1e65;intn;inta[N*2];longlongs[N*2];intq[N*2],head,tail;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cinn;for(inti1;in;i){cina[i];a[in]a[i];}for(inti1;in*2;i){s[i]s[i-1]a[i];}intans0;head1,tail0;for(inti1;in*2;i){while(headtails[q[tail]]s[i]){tail--;}q[tail]i;while(headtailq[head]i-n1){head;}if(in){intstarti-n1;if(startns[q[head]]s[start-1]){ans;}}}coutans;return0;}