P2629这道题最近在准备GESP六级和五级的圈子里讨论度挺高。它在洛谷上的定位是普及/提高的难度但放到GESP六级的考纲里恰好卡在“基础算法与数据结构综合应用”这个关键位置上。很多同学做这道题时代码能跑通样例一到评测就WA或者TLE然后就开始怀疑人生。其实这道题的核心难点不在思路本身而在于对“环形数组”的处理和“滑动窗口最值”的理解深度。今天我把这道题从题意拆解、算法推导到代码实现、调试坑点完整地捋一遍。1. 题目背景与核心考点解读1.1 这道题在考什么先快速回顾一下题面。有一串长度为n的整数首尾相连围成一个环。我们可以选择一个起点k从第k个数开始按顺时针方向依次经过全部n个数。在遍历过程中我们需要时刻维护一个“当前累计值”初始为0每经过一个数字就把它加进去。题目要求在遍历完全部n个数之前这个累计值任意时刻都不能为负数。问有多少个不同的起点k能够满足这个条件。这个问题描述得比较生活化叫“好消息坏消息”正数代表好消息负数代表坏消息累计值就是当前的心情指数你希望从头到尾心情都不跌到零以下。但是真正要解决它需要把故事翻译成数学语言否则容易往模拟的方向跑偏。从GESP的考纲来看这道题对应的核心考点主要有三个方向。第一个是前缀和Prefix Sum。如果原数组是a[1]到a[n]定义前缀和pre[i] a[1] a[2] ... a[i]。那么从第l个数到第r个数的区间和就是pre[r] - pre[l-1]。这道题要求“任何时刻累计值非负”本质上就是在考察某个起点开始的n个前缀和的最小值是否始终保持在某个参考值之上。第二个是单调队列Monotonic Queue。这是解决滑动窗口最值问题的标准工具。在这道题中我们需要在长度为n的“环展开链”上对每个位置维护长度为n的窗口内的最小前缀和。暴力做的话每个窗口都要扫一遍复杂度是O(n²)数据一大必挂。单调队列可以把每个窗口的最值维护降到均摊O(1)整体复杂度O(n)。第三个是环形问题的处理技巧。很多初学者看到“首尾相连”就懵不知道怎么把环转化成可以用线性结构解决的形式。这里有一个非常经典的套路叫“破环成链”简单说就是将原数组复制一份接到自己后面形成长度2n的数组这样从任意起点开始的长度为n的区间都能映射到这条线上的某个连续窗口。这三个考点单独拿出来都不是GESP六级的压轴级别但组合在一起就很有区分度。这也正是官方把它放在五级和六级交叉位置练习题里的原因它在考你“会不会把多个学过的基础技巧组合起来解决一个完整问题”。1.2 为什么这道题值得反复做说实话洛谷上难度相近的题有很多P2629能被大家反复拎出来练一定有它的独到之处。第一它的代码量非常小如果用C标准库的deque来实现单调队列核心代码可能不到四十行。这意味着你把它的思路吃透之后可以完全脱离题解独立写出来非常适合用来检验自己是否真正理解了“滑动窗口最值前缀和”的组合套路。GESP的六级考试代码长度通常不会很长但要求思路清晰、一次写对P2629的训练场景和真实考场高度一致。第二它的突破点其实很隐蔽。第一次做这道题的人大概率会想到两种思路一种是枚举起点然后模拟这很容易想到但也最容易超时另一种是试着用前缀和优化但很快会发现只靠前缀和不够因为你需要知道“任意时刻”的最小值而不是某个固定区间的前缀和。这种“行至山穷水尽”的感受恰恰是算法能力提升最快的时刻。第三GESP六级和七级的一个重点方向是“算法优化”具体体现在对时间复杂度的敏感度上。P2629的数据范围如果设置为n ≤ 10^6那O(n²)和O(n log n)都过不了必须O(n)。这能帮考生建立起一种非常重要的考试直觉看到“环形”想“破环成链”看到“区间最值”想“滑动窗口”看到“O(n)”想“单调队列”。这种条件反射式的直觉刷再多的简单题也建立不起来只有通过这种综合题才能练出来。2. 从朴素思路到最优解解题心路拆解2.1 朴素模拟为什么过不了拿到这个题目最容易想到的思路是什么呢直接模拟。假设数组长度为n我们用0下标和1下标两种习惯都行。枚举起点i从1到n然后从i开始往后走n步累加每个数如果过程中累加值变成负数就说明这个起点不行。所有起点都检查完后统计合法的起点数。这个思路完全正确没有任何逻辑漏洞但问题在于效率。每个起点最多走n步一共n个起点最坏情况下时间复杂度是O(n²)。如果n只有2000那随便跑但是洛谷P2629给出的最大数据规模一般是n≤10^6这样的量级具体以实际题目为准O(n²)在1秒时限下基本就是等死。可能有同学会说“我的C跑得快10^6的平方是10^12肯定跑不动。”对这个数据规模下O(n²)已经不只是“过不过”的问题而是“快到完全没戏”的问题。所以我们必须压缩复杂度到O(n)。在讲优化的思路之前想先插一句。很多初学者容易陷入一种误区就是拿到题就开始写代码写到一半发现超时才回头想优化。这种习惯在平时练习时危害不大但在考场上非常致命。GESP六级开始题目的数据规模设计得非常讲究通常就是为了卡掉暴力的。正确的做法是先看数据范围心里估算一下自己写出来的算法能不能过再动手写。回到这道题。既然O(n²)不行那就要想办法把“对每个起点都单独模拟一遍”这个过程变快。接下来我们需要做两件事一是把“环”拉直二是把“检查整个遍历过程”变成“查询某个区间内的最小值”。2.2 破环成链与前缀和先处理环。假设原数组是a[1]到a[n]。我们把它复制一遍接在后面形成一个长度为2n的数组b。比如a [3, -4, 5, 1, -2]那么b [3, -4, 5, 1, -2, 3, -4, 5, 1, -2]。为什么要这么做因为环上的任意起点比如从a[3]开始依次遍历5个数得到的是a[3], a[4], a[5], a[1], a[2]。在b数组里这一段恰好对应b[3]到b[7]这个连续的区间。也就是说环上“从任意位置截取长度n的连续段”这个操作在链上等价于“从一个位置开始取长度为n的连续子数组”。环的遍历问题就这样被转化成了线的区间问题这就是“破环成链”的基本思想。接下来引入前缀和。设原数组为a1下标。设pre[i]表示b数组前i个元素的和pre[0] 0。那么b[l]到b[r]的区间和就是pre[r] - pre[l-1]。现在重新看题意。假设我们选择起点k1≤k≤n那么在b数组中对应区间是[k, kn-1]。我们要保证从k出发遍历每一个元素的过程中累计值始终非负。如果我们把第k步时的累计值写成某个表达式会发现它正好等于某种“减去常数后的前缀和”。具体来说站在起点k时累计值初始为0。前t步的累计值等于b[k] b[k1] ... b[kt-1] pre[kt-1] - pre[k-1]当t1时就是b[k] pre[k] - pre[k-1]符合。要让这个过程任何时刻都非负实际上就是要求对所有的t∈[1, n]都有pre[kt-1] - pre[k-1] ≥ 0也就是pre[kt-1] ≥ pre[k-1]。换句话说从起点k开始能成功走完全程当且仅当在b数组的[k, kn-1]这个区间内所有位置j的前缀和pre[j]都不小于pre[k-1]。到这里问题就变得非常清晰了我们要找到所有k∈[1, n]使得pre[k-1] ≤ min(pre[k], pre[k1], ..., pre[kn-1])。这个转化是整个题目的灵魂。它把“模拟走n步”这种O(n)的单个起点检查变成“查一个区间的最小值”这种可以用数据结构快速完成的操作。如果对每个k都去扫描一遍区间复杂度还是O(n²)所以还需要最后一层优化滑动窗口。2.3 单调队列登场滑动窗口最小值现在的问题是我们有长度为2n1的pre数组注意pre[0]到pre[2n]需要依次求每个长度n的窗口的最小值窗口[k, kn-1]这里k从1到n。这个窗口的右端点最大是2n-1左端点最小是1所以总共需要查询n次。求固定长度窗口的最小值最好的办法就是用单调队列也叫滑动窗口最值。它的核心思想是维护一个双向队列队首到队尾的元素在数组中的下标是递增的但对应的pre值保持单调递增。这样队首永远是当前窗口的最小值。每当窗口向右滑动一位把新元素加入队列前从队尾开始弹出所有值大于等于它的元素因为那些元素比新元素老值又更大在后续任意窗口里都不可能成为最小值也就是“又老又没用”。这个动作保证了队列的单调性。把队列中已经滑出窗口的下标移除也就是“过期元素”。队首虽然值最小但如果它的下标小于当前窗口左端点它就已经不在窗口内了必须弹出。此时队首元素的下标对应的pre值就是当前窗口的最小值。这个过程每个元素最多入队一次、出队一次均摊复杂度O(1)整体O(n)。这就是为什么单调队列又快又优雅。可能有同学问为什么不直接用线段树或ST表因为这题要的是“定长滑动窗口”单调队列是专门为这个场景设计的写起来最短常数最小空间也省。线段树虽然也可以但代码量翻倍而且在GESP考试里没有必要引入那么重的结构。ST表也行但预处理O(n log n)不是最优。2.4 正确性证明的直观理解我们再用一个更直观的方式把“pre[k-1] ≤ min(...)”这个条件讲透不然很多同学就算代码写对了也解释不清楚为什么。想象你在玩一个跳格子的游戏。格子是b[k]到b[kn-1]每个格子上写着一个数可能是正可能是负你的初始“生命值”是0。每踩一个格子你的生命值就加上格子上的数。游戏要求你在走完所有格子之前生命值永远不能小于0。现在我们把每个格子上写的数换成“从起点到当前格子的累计变化量”。第一个格子的累计变化量就是b[k]第二个格子就是b[k]b[k1]依此类推。这些量放在pre数组里看就是pre[k] - pre[k-1]pre[k1] - pre[k-1]等等。所以“生命值始终≥0”就等价于“从起点到任意格子的累计变化量≥0”等价于“pre[当前位置] - pre[k-1] ≥ 0”等价于“pre[当前位置] ≥ pre[k-1]”。对“任意位置”取最严格的那个也就是要求“窗口内pre的最小值”不小于pre[k-1]。这个推导过程看似绕但本质上就是前缀和定义的自然展开。如果你在考场上卡住了我的建议是先在草稿纸上写下“累计值 pre[j] - pre[i-1]”然后问自己“要让这个式子对所有j都≥0最短缺的信息是什么”。答案往往就是“这个区间内最小的pre[j]”。一旦想通这一步后面就是纯模板操作了。3. 完整C实现与关键细节3.1 代码实现下面给出一个可以直接提交的C17版本。为了减少内存我没有真正构造一个长度为2n的数组b来存复制后的数据而是在计算前缀和的时候通过对原数组取模访问来模拟环。这样既省空间思路也更简洁。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long a(n 1); for (int i 1; i n; i) cin a[i]; vectorlong long pre(2 * n 1, 0); for (int i 1; i 2 * n; i) { // 利用取模技巧构造“破环成链”后的前缀和 pre[i] pre[i - 1] a[(i - 1) % n 1]; } dequeint dq; // 存的是pre数组的下标 int ans 0; // 先初始化第一个窗口 [1, n] for (int i 1; i n; i) { while (!dq.empty() pre[dq.back()] pre[i]) dq.pop_back(); dq.push_back(i); } for (int k 1; k n; k) { // 窗口左端点是k右端点是kn-1 while (!dq.empty() dq.front() k) dq.pop_front(); if (pre[dq.front()] - pre[k - 1] 0) ans; // 把右端点 kn 加入窗口下一次窗口 [k1, kn] int nxt k n; while (!dq.empty() pre[dq.back()] pre[nxt]) dq.pop_back(); dq.push_back(nxt); } cout ans \n; return 0; }3.2 核心步骤逐行解析有几点实现细节必须说明清楚。第一为什么pre数组要开2n1的长度。因为破环成链之后我们需要处理从b[1]到b[2n]的所有前缀和再加上pre[0]这个基准值总共需要2n1个位置。代码中我用pre[i] pre[i-1] a[(i-1)%n1]来避免真正把数组复制一遍。当i从1到2n时(i-1)%n1正好循环取a[1]到a[n]模拟了“b[i] a[(i-1)%n1]”这个映射关系。这一步的取模运算可能会让运行速度比直接拷贝数组慢一点点但对GESP的n最大规模来说没有任何压力。第二查询区间最小值时我们更新答案所依据的公式是windowMin - pre[k-1] 0即pre[dq.front()] - pre[k-1] 0。这里有同学会漏减pre[k-1]直接用pre[dq.front()] 0去判断那就会出大问题。因为前缀和pre[j]本身包含了一部分起点之前的数据累加不“去基准”的话相当于把b[1]到b[k-1]这些根本不属于本次遍历的数也算进来了。这一点我在后面“常见问题”里还会再强调。第三初始化第一个窗口时我们入队的是pre[1]到pre[n]的下标。这个窗口对应起点k1的情况左端点为1右端点为n。很多版本会从k1开始循环每次把右端点新元素入队、再把过期元素踢掉但这样第一个窗口在循环体里才被处理容易漏掉对dq.front() k的边界判断。所以更好的做法是先单独初始化第一个窗口然后再进入循环这样逻辑更清晰也方便调试。第四循环内部的顺序很讲究。先检查队首是否过期然后更新答案最后再把下一个右端点加入队列。顺序不能颠倒。如果先把新元素入队队首可能不再是当前窗口的最小值了新元素可能比原队首更小但它属于下一个窗口而我们当前要判断的还是旧窗口就会出错。这也是一个非常经典的手滑点。3.3 边界与初始化注意事项关于初始化有一个常见的坑队列的单调性质依赖于“值相等时弹出旧元素”。代码里我写的是pre[dq.back()] pre[i]时弹出。为什么是“”而不是“”如果两个元素的值一样旧元素的下标更小在未来的滑动中会先过期所以保留新元素、弹出旧元素是更优的选择。写“”也不会导致错误因为值相等时弹出谁对最小值判断没有影响但写“”可以让队列更“新鲜”队首元素过期时间更晚减少后续出队操作的次数常数几乎可以忽略不计但逻辑上更干净。还有一个边界k从1循环到n最后一次循环结束后nxt k n 2n这个下标在pre数组里是合法的因为我们开到了2n。为什么需要pre[2n]因为最后一个窗口是[k1, kn] [n1, 2n]右端点就是2n这个窗口虽然不会被用到起点k最多到n窗口终点是kn-1最大也就是2n-1但代码在最后一次循环里还是会先把nxt2n入队再退出所以数组必须能访问pre[2n]。如果你开数组时只开到2n-1会越界。这个问题很容易被忽视我在本地调试时第一次就把pre开成了2n结果样例报错排查了好一会儿才意识到是数组越界。另外题目本身没有明确说数据范围但如果a[i]的绝对值和n都很大的话前缀和可能超过int的表示范围。稳妥起见用long long来存pre。我在代码中已经把pre和a都声明为vector 。这个习惯建议大家从平时就开始养成涉及前缀和的题无脑用long long不会错。4. 常见问题与排查技巧实录4.1 样例过了却全WA常见是哪几种情况我自己做这道题的时候第一个AC版本并不是一次过的。当时遇到的第一个问题是“每个起点判断条件写反了”。我把条件写成了pre[dq.front()] pre[k-1]就认为不合法结果样例都过不了仔细检查后发现是把“最小前缀和不小于基准”的语义理解反了。这种情况属于思路层面理解错了代码语法再对也没用。建议大家在草稿纸上推导特别小的例子比如n3数组为[1, -2, 1]手动模拟一遍再对照代码看每个起点应该输出什么。这种题只要手动跑通一两个例子思路层面的错误基本能暴露。第二种常见的错误是“没有减去基准值”。比如直接用pre[dq.front()] 0来判断起点合法。这个错误在样例比较温和时不容易暴露因为如果数据是正数开头pre[dq.front()]恰好大于0可能判断结果碰巧是对的。但一旦数组开头有负数这种写法就会错得离谱。遇到这种“样例对但提交全WA”的情况可以自己构造一些有负数开头的case来验证。比如[ -1, 3, 2 ]理论上起点应该从第二个数开始才能成功-1开头瞬间就负了而用“不减去基准”的写法一定会把起点1也算进去。第三种是“窗口内最小值的下标判断错误”。因为我们是把b复制成2n长度的链来处理的所以窗口里的最小前缀和对应的实际位置j可能落在大n之后比如j n5这在原数组里其实就是b[5] a[5]属于环上的第5个元素。有些同学看到“如果j超过n就越界了”就开始怀疑算法实际上在链上这就是合法的。4.2 超时的排查方向如果你写的确实是O(n)的单调队列应该不会超时。但如果你用的是STL里的multiset或者priority_queue来维护窗口最小值复杂度是O(n log n)在n较小的时候可能也能过但n一旦上到10^6大概率就危险了。GESP六级的评测机配置一般有限1秒时限内O(n log n)与O(n)的差距会被放大。如果你用了multiset超时换成deque的手写单调队列基本能解决。如果已经是手写单调队列但还是超时那八成是在循环里写了死循环或重复入队。比如忘记在循环开始前弹出过期队首导致每个元素被重复扫了很多遍。这种情况下你可以在本地用一个很大的数据在关键位置用计数器打印队列长度来检查。另一个非常隐蔽的超时原因是关闭了同步但没有解除cin和cout的绑定。如果你用了#include bits/stdc.h且写了ios::sync_with_stdio(false); cin.tie(nullptr);那cin/cout本身问题不大。但如果你用的是endl而不是\n在有大量输出时也会拖慢速度尽管这道题输出只有一个数字影响不大但这个习惯建议改掉。4.3 一个容易踩的坑环的起点与下标映射还有一个小坑是关于输入数据的下标。很多同学喜欢把数组存成0下标即a[0]到a[n-1]然后破环成链时想用(i % n)来模拟。这确实是可行的后续代码逻辑也成立只需要在计算前缀和和窗口下标时保持一致即可。但要注意下标习惯不统一很容易导致bug。我的建议是不管用什么习惯先在纸上把下标映射表写出来再写代码。特别是k从1到npre[k-1]这种基准下标如果和0下标混在一起非常容易出错。另外一个更隐蔽的坑是关于“窗口长度n”的理解。有同学把窗口长度写成了n-1理由是起点k本身已经算了一个元素剩下的只需要n-1个。这种理解是错误的。我们真正要检查的是从起点开始走过全部n个数字。在pre序列里这对应窗口[k, kn-1]长度是n。比如n5起点k1时窗口是[1,5]长度5对应b[1]到b[5]这5个数的前缀和。窗口长度错了答案一定错。5. 举一反三遇到类似题目怎么想5.1 P2629的兄弟题目如果P2629已经能轻松AC建议趁热打铁做几道思路相似的题目把“环形前缀和单调队列/贪心”的组合套路彻底固化。洛谷上有一道比较经典的题叫P1886滑动窗口最值模板题单纯考察单调队列。如果你看P2629时感觉单调队列部分还不够熟先去把P1886刷了然后回来看P2629就能明显感觉到自己哪里通了。还有一道牛客或洛谷上常见的“环形区间和最大”类题目比如求环形数组的最大子段和。解法和P2629类似都是先破环成链再用前缀和和数据结构维护。这种题练习的目的是让你形成“看到环就想到拆环”的条件反射而不是遇到环形就傻眼。另外还有一类“坏消息好消息”的变体比如把“累计值不能为负”改成“累计值不能大于某个上限”那本质上就变成了维护窗口内最大/最小值的双向约束可能需要同时维护单调递增队列和单调递减队列。这种变体当作进阶训练很有意思也能帮你更深入地理解单调队列为什么是“单调”的。5.2 GESP考试中的高频考点关联从GESP四级到六级的知识分布来看前缀和和差分是六级最常考的基础算法之一而单调队列在官方考纲里并不算六级的新增内容但它经常作为“优化手段”出现。也就是说考官不会直接说“请写一个单调队列”而是会精心构造一道题让“不用单调队列就超时”迫使你用到它。P2629就是非常典型的这种题知识点名字里没有“单调队列”但解法里绕不开它。与此对应的GESP六级还经常会考到二分答案前缀和的组合、贪心堆优化、图论基础里的最短路等。这些内容的共同点是单个知识点你全会但组合起来需要你有“算法设计”的意识。P2629的训练价值就在于它教会你“如何把问题一步两步地转化到已知的模板上”。第一步把环变链第二步把路径合法性转成区间最小值比较第三步套单调队列模板。每一步都是独立的基础能力串联起来就是完整的算法思维。还有一个常被忽视的考点是“数据范围分析”。GESP的题目一般会明确给出n的范围。学会读题后先估算自己算法的时间复杂度和空间复杂度再决定编码方案这在六级开始是必备素养。P2629如果用朴素模拟代码可能只有十行但拿不到分用单调队列代码翻倍但能过。这本身就是一次深刻的教训算法比赛不是比谁代码短而是比谁更懂数据规模背后的信息。最后想说GESP七级的方向会更硬核会涉及动态规划、树、贪心进阶等内容。六级到七级之间这种“综合思维能力”的过渡非常关键。P2629作为六级和五级交叉难度的一道练习题正好长在这个过渡带上。刷题不能只追求AC要逼自己把每一步转化都讲清楚、写干净。能把这道题的思路给同学讲明白你对前缀和、单调队列、环形处理的理解基本就过关了。我个人在实际操作中的体会是这道题用代码跑通一遍只是入门真正有价值的是你把它反复拿出来用不同的数据结构去实现先用deque写再用数组手写单调队列模拟双端队列最后试着用线段树去解一遍不提交、纯思考。这样折腾几次之后你会对“为什么这道题最优解是单调队列”有一个远超课本的理解。以后再遇到和P2629类似的题你的第一反应就不会是“这题好难”而是“这不就是破环成链加滑窗吗”。这种感觉就是刷题量变到质变的节点。
