今天的每日一题是蓝桥杯真题里的拔河。我点开题面第一反应是“这题是不是把所有人力量排序然后找相邻差值最小就行”结果越读越不对劲——人家根本没让你把队伍打乱重排而是必须在一排人里选出两个连续区段并且两个区段不能重叠。这一下就从“早就做烂的贪心”变成了“两个不重叠区间的匹配问题”难度直接上一个台阶。如果你也在准备蓝桥杯省赛或者想练一练“区间集合 离线扫描”这类处理手法这道题值得认真啃一遍。我前前后后写了三版代码从 O(n^4) 暴力改到 O(n^2 log n) 扫描线中间踩了好几个坑这篇题解干脆把整个思考过程、代码实现和坑点全部整理出来省得你再去翻十几篇零散的博客。1. 题目拆解与坑点预警1.1 拔河到底考什么先快速过一遍题面。题目大意是这样有 n 个人排成一排第 i 个人有一个力量值 a[i]。现在要组织两支拔河队伍每支队伍必须是原序列里连续的一段也就是说队伍选的是区间 [l, r]人数至少 1。两支队伍不能有交集可以有间隔。我们的目标是让两支队伍的力量总和尽可能接近求两队力量之差的绝对值的最小值。举个最简单的例子如果力量值是[1, 2, 3, 4]你可以选第一队[1,2]加起来是 3第二队[3]是 3差值就是 0。注意这里第一队的右端点是 2第二队的左端点是 3两者没有重叠完全合法。这道题真正考的不是“怎么分组”而是“如何在大量连续区间和中快速找到一对不重叠的区间使它们的和尽量接近”。很多新手容易先想到背包、DP、二分答案这些方向的都是被“拔河”这个背景带偏了。拔河只是一个壳本质是区间问题。1.2 数据范围决定算法选型题目给了 n 的范围我记得正常版本是 n ≤ 1000力量值可以到 10^9 级别。如果你只看 n ≤ 1000会误以为 O(n^3) 暴力也能过但实际上力量值大到需要用 long long 存区间和而且后面优化到 O(n^2 log n) 也才勉强算是“稳过”。这里有一个很常见的误判看到 n1000觉得 O(n^3) 是 10^9 次操作在蓝桥杯的数据下大概率超时O(n^4) 更是想都不要想。所以第一步就得定方向至少得是 O(n^2 log n) 或 O(n^2) 的级别。另外一个容易被忽略的点是区间数量是 n * (n 1) / 2n1000 时大约 50 万个区间。这个数量级是后面所有优化分析的基础。2. 思路演进从暴力枚举到扫描线二分2.1 暴力为什么不可行最朴素的做法是枚举两支队伍分别的左右端点也就是四层循环。外层枚举第一队 [l1, r1]内层枚举第二队 [l2, r2]先判断两个区间是否重叠不重叠就计算力量和的差不断更新最小值。这个做法的复杂度是 O(n^4)n1000 时直接爆炸。就算用前缀和把区间和从 O(1) 算出来四层循环的常数再小也撑不住。我实测过 n200 的时候就已经卡得明显n500 基本跑不动蓝桥杯的数据肯定过不了。所以必须把“枚举四个端点”压缩成“枚举两个区间级别”的复杂度。核心思路是能不能把所有可能的区间和都算出来然后只比较那些“有可能接近”的区间对2.2 不重叠条件的转换如果两个区间不重叠那么一定有一个区间在另一个区间的左边。假设左边的区间是 L右边的区间是 R那么满足的不重叠条件就是L.r R.l也就是说左边区间的右端点要严格小于右边区间的左端点。这个条件非常关键它把“两个区间不能重叠”从一个二维关系变成了一个可以用于排序扫描的顺序关系。那问题就变成对每一个右区间 R我们想在所有“右端点小于 R.l”的左区间中找到一个区间和与 R 的区间和差值最小。如果能把满足条件的左区间都维护在一个数据结构里每次查询最接近的值问题就迎刃而解。2.3 离线扫描线的巧妙之处这里我用的是“离线扫描线 multiset 二分”的做法。思路分三步第一生成所有区间的信息包括左端点 l、右端点 r、区间和 s。第二把所有区间按左端点从小到大排序得到一个扫描顺序 byL。另一个数组按右端点从小到大排序记为 byR。第三用一个指针 ptr 在 byR 上从左往右移动。当我们扫描到某个区间 cur 时就把 byR 中所有满足 r cur.l 的区间和插入到 multiset 里。这些区间都严格位于 cur 的左侧和 cur 完全不重叠。然后在 multiset 中二分查找最接近 cur.s 的值更新答案。为什么这样不会漏掉最优解假设最优解的两个区间是 L 和 R且 L 在 R 的左侧也就是 L.r R.l。当扫描线处理到 R 时所有 r R.l 的区间都已经插入 multisetL 当然也在里面。所以我们在查询 R 的时候就一定能看到 L。换句话说每一对不重叠区间都会在“右侧区间被扫描到”的那个时刻被发现。如果最优解里 R 在 L 的左边呢那就把两个区间对调一下定义左边那个叫 L、右边那个叫 R同样成立。所以这个扫描过程覆盖了所有情况。2.4 复杂度分析与另一个方案对比区间总数为 m n*(n1)/2。生成所有区间和是 O(n^2)。排序 byL 和 byR 各是 O(m log m)。扫描过程里每个区间插入一次、查询一次multiset 操作都是 O(log m)。所以总复杂度是 O(m log m)也就是 O(n^2 log n)。n1000 时 m 大约是 50 万排序和 multiset 完全没压力运行时间在几百毫秒级别。还有一个很多人会想到的思路是“枚举分割线”把原序列切成左右两部分然后枚举左边所有区间与右边所有区间配对求最小差值。这个思路理论上对但实现时要么是 O(n^3) 级别的重复枚举要么需要动态维护左右两组区间和集合插入删除比较麻烦。扫描线做法相当于把“分割线”变成了“按右端点顺序插入”的离线过程逻辑更简单也不容易写错。3. 完整代码与逐段解析3.1 代码实现下面是我最终 AC 的 C 代码基于 C17 编写蓝桥杯环境也能直接编译运行。#include bits/stdc.h using namespace std; struct Seg { int l, r; long long s; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long a(n 1), pre(n 1, 0); for (int i 1; i n; i) { cin a[i]; pre[i] pre[i - 1] a[i]; } vectorSeg byL, byR; byL.reserve(n * (n 1) / 2); byR.reserve(n * (n 1) / 2); for (int l 1; l n; l) { for (int r l; r n; r) { long long sum pre[r] - pre[l - 1]; byL.push_back({l, r, sum}); byR.push_back({l, r, sum}); } } sort(byL.begin(), byL.end(), [](const Seg x, const Seg y) { if (x.l ! y.l) return x.l y.l; return x.r y.r; }); sort(byR.begin(), byR.end(), [](const Seg x, const Seg y) { if (x.r ! y.r) return x.r y.r; return x.l y.l; }); multisetlong long S; long long ans LLONG_MAX; int ptr 0; int m (int)byR.size(); for (const Seg cur : byL) { while (ptr m byR[ptr].r cur.l) { S.insert(byR[ptr].s); ptr; } auto it S.lower_bound(cur.s); if (it ! S.end()) { ans min(ans, *it - cur.s); } if (it ! S.begin()) { --it; ans min(ans, cur.s - *it); } } cout ans \n; return 0; }这段代码看着不长但每一块都有讲究。下面拆开说。3.2 区间和生成与前缀和我在这里用的是 1-based 下标这样前缀和的公式写起来更直观。pre[i]表示前 i 个元素的和区间 [l, r] 的和就是pre[r] - pre[l-1]。有两层循环生成所有区间。这里我同时往 byL 和 byR 里 push 相同的区间数据是因为后面需要按不同的关键字排序。如果你担心空间浪费可以先只生成一个数组拷贝后再分别排序效果一样。我测试下来的结论是用两个 vector 直接存代码好写内存也不会炸后面会专门分析内存占用。生成区间这步看起来简单但容易被坑的是sum必须用long long。如果 a[i] 是 10^9 级别n1000一个区间的和最大到 10^12int 肯定装不下。3.3 排序与扫描线核心byL 按左端点升序排序这样扫描时 l 是单调递增的。byR 按右端点升序排序目的是让我们能用一个移动指针 ptr把所有右端点足够小、可以安全放进候选集合的区间逐个加入 multiset。核心 while 循环的条件是byR[ptr].r cur.l。这个条件翻译过来就是候选区间的右端点必须严格小于当前区间的左端点。两个区间没有重合部分是一个合法的左右放置关系。这里为什么用multiset而不是set因为可能存在多个不同的区间拥有完全相同的区间和而set会去重会导致漏掉答案。我实际调试时就是一开始图省事用了set结果有两组数据始终偏大换成multiset之后立刻正确。插入逻辑保证了 multiset 里的所有区间都是“在当前区间左侧”的。接下来要用lower_bound二分查找最接近 cur.s 的值。这里有两个候选it指向第一个不小于 cur.s 的值也就是大于等于当前区间和的最小值差值*it - cur.s是非负的。it的前一个值也就是小于 cur.s 的最大值差值cur.s - *it非负。取这两个的较小值更新 ans。如果 lower_bound 返回的是 begin()说明没有比 cur.s 小的值那就只考虑第一个情况如果返回 end()说明所有值都比 cur.s 小那就只考虑第二个情况。3.4 正确性再验证我在写代码之前其实担心过一个问题扫描到某个右侧区间 cur 时左侧候选区间已经插入但如果那个左侧区间的左端点比另一个更左的区间更晚插入怎么办其实没有影响因为插入的顺序只由右端点决定和左端点无关。只要左边区间的右端点小于 cur.l它就一定会在某个时刻被插入而且插入之后一直留在 multiset 里不会被删除。那么会不会出现一个左侧区间虽然右端点满足条件但它的左端点比 cur 的左端点还靠右以至于两个区间其实还是重叠的不会。因为判断条件是r cur.l这个条件已经杜绝了所有重叠情况。左侧区间无论左端点在哪它的右端点都在 cur 的左端点左边整个区间自然完全在 cur 的左边。每个多区间对只在右侧区间被处理时匹配一次左侧区间只是作为静态候选项存在所以不存在重复计算的问题。3.5 内存与时间实测n1000 时区间总数是 500500。每个 Seg 包含两个 int 和一个 long long按内存对齐大约是 16 字节两个 vector 总共约 16MB。multiset 底层是红黑树每个节点约有 40 字节左右的开销最多同时存 50 万个节点约占 20MB 到 25MB。加在一起也就是 40MB 出头在蓝桥杯常见的 128MB 或 256MB 内存限制下完全没问题。时间上排序 50 万个元素两次加上 50 万次 multiset 插入和二分查询我自己本地跑最坏数据大约是 0.3 秒。蓝桥杯的时间限制一般是 1 秒或 2 秒这个表现足够稳。如果哪天遇到 n5000 的版本这个做法内存会飙到难以接受因为区间数是 1250 万。那就得考虑更紧凑的方案比如只存区间和和右端点索引配合树状数组做离线查询。不过这题正常数据范围就是 1000扫描线版本是我觉得最好理解又最容易写对的一版。4. 测试用例与实战避坑4.1 几组必须跑的数据我刷题时习惯先用样例跑通再做几组手造数据验证边界。这里分享几组我用过的测试数据。第一组n4a [1,2,3,4]答案是 0。取第一队[1,2]和第二队[3]力量都是 3。这组数据能验证“相邻但不重叠”的情况。第二组n3a [5,5,5]答案是 0。取[1]和[2]力量都是 5。第三组n2a [1,2]答案是 1。只有[1]和[2]两个单元素区间可选。第四组n5a [3,1,4,1,5]这组我算出来最优是 0选[1,2]和为 4选[4,5]和为 6差 2选[3]和为 4选[5]和为 5差 1再仔细看可以取第一队[1]3第二队[2,3]5差 2最优其实是第一队[4]1第二队[2]1差 0。这说明答案不一定来自大区间单元素区间也会是答案来源。建议你把这几组数据直接贴进代码里跑一遍输出和预期一致基本就说明核心逻辑没大问题。4.2 实战中容易踩的三个坑第一个坑是区间和必须用 long long。我有一次把结构体里的 s 定义成了 int本地测试小数据没问题换到大数据直接错。因为区间和很容易超过 2^31尤其当力量值接近 10^9 时两个 10^9 相加就已经溢出。第二个坑是 multiset 和 set 的区别。前面提过两个不同区间可能拥有相同的区间和用 set 会把重复值合并导致差的绝对值被错误放大。如果题目数据中恰好出现多个区间和相等set 版本就会漏解。所以这里必须用 multiset。第三个坑是二分查询时要同时看 lower_bound 返回的迭代器和它的前一个迭代器。很多题解只写了it lower_bound(cur.s)然后更新*it - cur.s这样只能找到“不小于当前值”的候选漏掉了“小于当前值但非常接近”的情况。比如当前区间和是 100multiset 里只有 99 和 101只更新 101 这边就会把正确答案 1 漏成 2。另外还有一个容易被忽略的细节检查it ! begin()时要先通过 lower_bound 拿到迭代器再做--it。不要直接用一个独立迭代器遍历整个 multiset那样复杂度会退化。二分查找本身就是 O(log m)每次查询只用两次迭代器操作。4.3 这道题对后续刷题的启发拔河这题让我对“区间 不重叠”这类问题有了一个固定套路凡是要求两个不重叠区间之间的关系基本都能试着转化为扫描线的顺序问题。先确定一个区间作为“基准”把所有满足右端点小于基准左端点的区间维护到数据结构里然后查询最优值。这个套路在后来的“矩阵面积”、“区间选点”等题目里反复出现。还有一个收获是拿到题目先不要急着写暴力花两分钟想清楚能不能用扫描线的思想降维。暴力四层循环谁都会写但蓝桥杯省赛的区分度就在于能不能把 O(n^4) 降到 O(n^2 log n)。这类优化题你只要吃透一道后面遇到相似的题就完全不怕了。我个人的习惯是每道题 AC 之后在代码旁边写一段自然语言注释记录这道题的核心转化点。拔河这题我写的是“不重叠 排序后右端点小于当前左端点离线插入 multiset”。过了几个月再翻这段笔记还能回忆起完整的思考路径。最后再分享一个小技巧调试扫描线题时如果答案始终偏大不要急着怀疑二分逻辑先检查 multiset 里插入的区间是否符合“严格左侧”的条件我一开始就把写成了导致把自己的左邻区间也算进去了答案被污染。这种边界问题在区间题里特别容易犯写的时候多念叨两遍“右端点小于不是小于等于”。
