拔河是蓝桥杯每日一题里我印象很深的一道题。题目本身不长但你第一次看到多半会卡在怎么枚举才不超时上。今天把这题的完整思考过程、代码和踩坑记录都整理出来希望对正在刷蓝桥杯真题的你有所帮助。这道题在蓝桥杯C/C组、Python组都出现过类似的考法核心考的是前缀和、区间枚举和排序找最优这三个基本功的组合非常适合拿来练手。1. 先搞清楚拔河题在问什么1.1 题面拆开看拔河题的题面描述很生活化有一排同学每个同学有一个力量值现在要选出两队参加拔河。每一队必须是原来队伍中连续的一段也就是你不能跳着选人。要求两队不能有重叠的同学然后让两队的总力量之差尽可能小输出这个最小差值。把生活场景翻译成算法语言就是给你一个长度为n的数组a让你选出两个不重叠的连续子区间记区间和分别为S1和S2求|S1 - S2|的最小值。这里有两个关键词需要注意第一个是连续这意味着区间可以用左端点l和右端点r唯一表示第二个是不重叠也就是说两个区间不能共享任何一个同学。有的题目版本还会多一句两队人数尽量接近比如人数相等或者差一个人。如果是这种情况只需要在更新答案之前额外判断一下两个区间的长度差是否满足要求即可核心解法不变。蓝桥杯历年真题中的版本我印象里主要卡的就是区间和的差值所以这篇文章先按最经典的不重叠双区间版本讲。1.2 为什么暴力枚举会超时很多第一次接触这道题的同学第一反应就是直接枚举。外层循环枚举第一队[l1, r1]内层循环枚举第二队[l2, r2]判断两个区间没有交集然后计算力量差。这确实是最朴素的想法但算一下复杂度区间对的数量大约是O(n^4)n稍微大一点就完全跑不动。我举个例子如果n1000四个循环再加上区间求和操作次数轻松超过10^12这个量级哪怕计算机每秒钟能跑10^9次运算也要跑一千秒以上这显然不可能通过。而且蓝桥杯省赛的时限通常是1到2秒暴力枚举连小数据都危险。所以说这道题第一个要解决的问题就是如何减少枚举量。顺着这个思路往下想两队的力量差只跟区间和有关那我们是不是可以先想办法快速算出任意区间的和这就引出了前缀和这个经典工具。2. 前缀和把区间和变成O(1)查询2.1 前缀和数组怎么建前缀和的核心思想很简单用一个数组s其中s[i]表示数组前i个元素的和。这样任意区间[l, r]的和就可以用s[r] - s[l-1]直接算出来无需再循环累加。举个例子数组a [2, 3, 1, 4]前缀和数组s [0, 2, 5, 6, 10]。想求第2个到第3个元素的和也就是314直接用s[3]-s[1]6-24一步到位。这里的下标我从1开始这样s[0]0作为一个天然的边界代码写起来非常干净。前缀和的好处不仅仅是省时间更重要的是它在逻辑上把区间求和这个子问题彻底解决了。不管后面是排序、二分还是双指针我们都不需要再关心区间内部长什么样只需要关心区间和本身。这也是很多区间类题目的通用套路先预处理前缀和再枚举区间时间复杂度直接从O(n^3)以上降下来。2.2 枚举所有候选区间现在我们可以把注意力放在区间集合上。n个元素能组成多少个连续区间以左端点l为1到n右端点r为l到n总共是n*(n1)/2个。对于n1000大约是50万个区间这个数量完全可以在1秒内处理完。枚举的过程就是把所有区间都找出来把区间和以及左右端点存起来。为什么要存左右端点因为后面判断两个区间是否重叠时必须要知道它们的位置。这里存区间和的数组长度是50万排序一次的时间大约是50万乘以log(50万)也就是千万级别的操作完全可行。你可能会问为什么要把所有区间和都拿出来而不是直接在原数组上想办法因为两队力量差最小本质上是在50万个区间和中找两个最接近的数同时要求这两个数对应的区间不重叠。找最接近的两个数最直接的办法就是排序后找相邻项。这就把二维的区间问题转化成了一个一维数组上的最近邻问题。2.3 排序后相邻项才是最优候选先抛开不重叠这个限制单纯看50万个区间和。如果要从这些数里找两个差值最小的数最优答案一定出现在排序后的相邻位置。道理很直观把所有数按从小到大排好如果你在中间某个数x右边找另一个数y让差值最小那么y一定是x右边离它最近的那个数也就是x的下一个元素同理往左边找就是上一个元素。跳过不相邻的元素差值只会更大。所以解题思路一下子清晰了先把所有区间按区间和从小到大排序然后遍历一遍只检查相邻两项的差值同时用左右端点判断这两个区间是否重叠。如果重叠就跳过这一对如果不重叠就更新答案。你可能会担心万一最优的两个区间在排序后不相邻中间隔着别的区间那是不是就漏掉了这个担心很合理实际操作中确实要考虑。但可以这样理解如果两个区间和之间存在一个中间值cc与左边区间和的差值肯定小于原来那对的差值那c对应的区间要么能构成更优解要么与两边区间重叠导致不合法。在蓝桥杯这道题的数据范围下排序后相邻枚举是目前最主流的写法实测可以通过所以不用过度纠结证明先把方法用熟。3. 不重叠区间判断与C实现3.1 结构体里存什么排序的时候我们不能只存一个区间和因为排序后还要判断两个区间是否重叠。所以需要一个结构体至少包含三个字段区间和sum、左端点l、右端点r。结构体可以这样写struct Node { int sum; int l, r; };排序的时候按照sum从小到大排。由于我们需要的是sum相邻的区间sort默认按第一个字段比较就行如果担心稳定性和特殊数据可以自己写一个比较函数bool cmp(const Node a, const Node b) { return a.sum b.sum; }这里有个小细节left和right都存1-based下标。区间[l, r]的长度是r-l1所以如果题目要求两队人数接近你可以顺便在结构体里加一个len字段更新答案前判断一下两个区间的长度差是否满足条件。3.2 判断两个区间是否重叠两个区间不重叠的定义是它们没有共同的元素。用闭区间[l1, r1]和[l2, r2]表示不重叠的条件是r1 l2 或者 r2 l1。对应到C代码就是if (a.r b.l || b.r a.l) { // 不重叠更新答案 }这里最容易犯错的是边界。比如第一个区间是[1, 2]第二个区间是[3, 4]这两个区间没有共同的同学是合法的。此时r12l23满足r1 l2。但如果你把条件写成了r1 l2那[1,2]和[2,3]也会被算成不重叠实际上它们都包含第2个同学属于重叠区间会出问题。所以切记是严格小于而不是小于等于。反过来说区间[1, 2]和[2, 3]是重叠的因为它俩都包含2号同学因此不能作为两支队伍。判断的时候只要r1 l2不成立就说明至少有一个共同元素。3.3 完整的C代码下面给出可以直接提交的C版本代码我加了注释方便你对照理解#include bits/stdc.h using namespace std; const int N 1005; int a[N], s[N]; struct Node { int sum; int l, r; bool operator (const Node other) const { return sum other.sum; } }; vectorNode v; int main() { int n; cin n; for (int i 1; i n; i) { cin a[i]; s[i] s[i - 1] a[i]; } // 枚举所有连续区间存下区间和以及左右端点 for (int l 1; l n; l) { for (int r l; r n; r) { v.push_back({s[r] - s[l - 1], l, r}); } } sort(v.begin(), v.end()); int ans INT_MAX; for (int i 0; i 1 (int)v.size(); i) { // 跳过重叠区间只计算不重叠的两个区间 if (v[i].r v[i 1].l || v[i 1].r v[i].l) { ans min(ans, abs(v[i 1].sum - v[i].sum)); } } cout ans endl; return 0; }这段代码在n1000的时候区间总数为大约50万个排序一次和线性扫描一次时间开销非常小蓝桥杯C/C组完全够用。代码里用到了bits/stdc.h这个头文件蓝桥杯的gcc环境是支持的放心用。还有一个小优化点求答案的初始值。如果题目保证所有人力量值都是正整数那么最大差值不会超过所有区间和的最大值减最小值用INT_MAX作为初始值最稳妥。如果写成0后面永远min不到更小的值输出就会一直是0这种低级错误在考场上很容易犯。4. Python版本与运行效率4.1 Python代码怎么写Python组参赛的同学也不用慌逻辑完全相同只是语法不同。这里我给出一个清晰可读的版本def main(): import sys input sys.stdin.readline n int(input()) a list(map(int, input().split())) # 前缀和s[0] 0 s [0] * (n 1) for i in range(1, n 1): s[i] s[i - 1] a[i - 1] intervals [] for l in range(1, n 1): for r in range(l, n 1): intervals.append((s[r] - s[l - 1], l, r)) # 按区间和排序 intervals.sort(keylambda x: x[0]) ans 10 ** 18 for i in range(len(intervals) - 1): sum1, l1, r1 intervals[i] sum2, l2, r2 intervals[i 1] if r1 l2 or r2 l1: ans min(ans, abs(sum2 - sum1)) print(ans) if __name__ __main__: main()这段代码用元组存储区间信息排序时按第一个元素也就是区间和排序。Python的元组比较也是按顺序比较元素所以直接用sort()也是可以的。不过为了可读性我还是写清楚了keylambda x: x[0]。需要注意Python在n1000时性能是可以接受的大约50万个区间排序和循环都很快。但如果你用Python跑n5000的数据区间数量会变成大约1250万个内存和时间都会紧张。蓝桥杯Python组的题目数据通常会照顾Python的运行效率但还是建议提前有意识地把枚举过程中的常数写小一点比如少用嵌套函数、用局部变量缓存s等。4.2 复杂度与赛时取舍这道题的复杂度是O(n^2 log n)空间复杂度O(n^2)。具体来说枚举区间是O(n^2)排序是O(n^2 log n)最后的线性扫描是O(n^2)。对于n100050万这个数量级非常轻松对于n50001250万这个数量级在C里也能勉强跑Python就要看运气了。如果你在赛场上遇到n范围更大的变式题还可以进一步优化把排序后扫描的步骤换成双指针或者二分查找甚至可以用multiset动态维护区间和。不过这些优化属于进阶玩法蓝桥杯这道题的标准解法用上面的代码就够了。先把基础版本吃透再想优化不迟。有个细节可以分享在C里vector的push_back会有扩容开销如果你提前知道区间数量是n*(n1)/2可以先调用reserve预留空间减少动态扩容的耗时。代码加一行v.reserve(n * (n 1) / 2)就行算是锦上添花的小优化。5. 新手最容易踩的坑5.1 重叠条件写反这是最常见的错误我见过很多同学写判断重叠的时候把条件写成了r1 l2 r2 l1然后在后面用!来取反。逻辑上没错但写错一两个符号就容易出bug。我的建议是用不重叠条件直接判断也就是r1 l2 || r2 l1。这样语义最清晰不用绕弯子。写代码的时候先画一个坐标轴两个区间分别在左边和右边边界关系一目了然然后再落笔写条件。5.2 答案初始值设置ans的初始值一定要设成一个很大的数C用INT_MAX或0x3f3f3f3fPython用10**18。如果初始值设成0那么任何正的差值都无法更新ans最后结果永远是0样例过了但大数据全错。顺便提一下0x3f3f3f3f在算法竞赛里很常用因为它足够大而且两个0x3f3f3f3f相加不会溢出int范围。但对于这道题我们只涉及单个ans的初始化和min操作用INT_MAX就够了。5.3 遗漏区间相邻的合法情况区间[1, 2]和[3, 4]没有共同元素是完全合法的两支队伍。有些同学写不重叠判断时会误以为两个区间只要挨着就算有交集于是写成r1 1 l2这就把合法情况过滤掉了可能导致答案偏大。记住判断重叠的唯一标准是有没有共享下标。区间[1,2]和[3,4]没有共享下标合法区间[1,3]和[3,5]共享下标3不合法。边界处用严格小于号就不会有这种问题。5.4 易错点速查表易错点错误写法正确写法后果重叠判断r1 l2r1 l2把共享边界判成合法答案偏小答案初始值ans 0ans INT_MAX / 10**18答案永远不更新区间存储只存sum存sum, l, r无法判断重叠排序范围只排序前一半区间排序所有n*(n1)/2个区间漏掉候选答案枚举区间从0到n-1从1到nr从l到n下标混乱越界或漏解这张表是我自己刷题时总结出来的考试前过一遍很有用。很多WA不是思路问题就是这些细节问题。5.5 如果你遇到两队人数接近的版本我再多说两句。有些拔河变式题会明确要求两队人数相等或者相差一人。遇到这种情况不要在思路上大改只需要在结构体里多存一个长度字段len更新答案前加一个判断if (abs(v[i].len - v[i 1].len) 1) { ans min(ans, abs(v[i 1].sum - v[i].sum)); }这个判断不会改变算法的主框架。如果你是在蓝桥杯真题里遇到原题我印象中它是不需要这个长度限制的但如果题目描述里明确写了就按上面这样加一行稳得很。6. 从拔河题看蓝桥杯备赛6.1 每日一题怎么刷才算数蓝桥杯每日一题这个系列很多人在跟但刷题效果差距很大。我的体会是每天一道题不是做完就完了一定要记录这道题用了什么算法、自己卡在了哪里、题解里哪个转化是没想到的。拔河题就是一个很好的记录样本它把前缀和、枚举、排序三个点串在一起你把它整理成一篇笔记比单纯刷十道重复的简单题有价值得多。具体操作上我建议先独立思考20到30分钟如果完全没有头绪再去看题解。看完题解不是抄代码而是要把思路用自己的话复述一遍然后关掉题解重新写。很多同学卡在看得懂但写不出来就是因为缺少这个复述和重写的环节。6.2 遇到新题怎么套模板拔河题这种先枚举所有可能再排序找最优的思路本质上是区间类问题的通用模板。类似的题还有给一个数组选两个区间使某个指标最大或最小给一些区间找和接近的两个区间等等。碰到这种题第一反应就可以尝试前缀和加上排序。另外蓝桥杯C/CB组和A组的出题风格其实很一致常考的知识点就那么几个前缀和与差分、二分、贪心、动态规划、搜索、图论基础。你在刷蓝桥杯历年真题的时候可以按知识点给题目打标签到考前冲刺阶段直接按标签复习效率会高很多。6.3 考前一个月怎么安排距离16届蓝桥杯省考这种大节点我的建议是真题优先模拟题辅助。每天保持一两道有质量的算法题周末做一次完整的模拟赛按真实考试的时间和环境来。代码题之外如果参加的是单片机或嵌入式组客观题也不能丢每天抽一点时间过知识点保持记忆热度。模拟赛的作用是让你习惯题目做不完的紧张感。蓝桥杯的题量不算小碰到拔河这种中等偏上的题要在考场上冷静做出正确复杂度分析平时就要养成习惯每道题先思考数据范围估算复杂度再决定是暴力还是优化。这个习惯比多背几个模板更重要。最后再分享一个我个人的小经验做拔河题的时候我当时写完代码过了样例又自己构造了几个小数据去验证比如全是相同力量值的情况、区间刚好相邻的情况、只有一个区间的情况。这些边界测试帮我发现了重叠判断里的边界问题。比赛时如果时间充裕建议你也多测几个极端数据这比反复看代码找错更管用。这道题的下一招你可以试着把它改成求差值最大、或者输出具体方案锻炼一下举一反三的能力。