GESP八级真题拆解：区间合并与贪心算法，从接竹竿到建模思维

2024年3月GESP八级认证，C++组的编程题里有一道“接竹竿”，我印象非常深。这题初看是个生活场景模拟，但真正动手之后会发现，它本质上是一道非常典型的区间连通性问题，考察的是你把“题目描述”抽象成“数学模型”的能力。GESP八级作为最高等级，考的就是这种区分度——题面包装得很朴素，背后的算法却是实打实的排序+贪心。这篇文章就把这道题的完整拆解写下来，从题面还原、建模思路、C++实现，到考场上的易错点和扩展变体，一次性讲透。适合正在备考GESP八级、或者想补一补区间类算法基础的同学参考。

1. 先聊聊GESP八级在考什么

1.1 八级的难度定位与考察范围

GESP一共八个级别，八级是顶格。到了这个级别，考点已经不只是“会不会写循环”了，而是要求考生具备一定的算法设计和建模能力。官方大纲里列出的内容大致包括：树和图的基础操作、常见排序算法的复杂度分析、动态规划入门、贪心思想、以及STL的熟练使用。编程题通常有两道，分值占比很大，第一道往往偏模板题、考基本功，第二道就是“接竹竿”这种需要多转一层弯的题。

拿“接竹竿”来说，它表面讲的是竹竿、跳跃、行走，实际考的就是区间合并。这种出题风格近几年越来越常见，不是在题目里写“给你n个区间，求合并后的总长度”这种直白表述，而是把区间藏在一个生活场景里，让你自己把它挖出来。八级考生能不能从一堆文字描述里识别出“这是区间问题”，直接决定了这道题能不能拿满分。

1.2 “接竹竿”的考点映射

这道题真正考察的东西，我从高到低排一下：

• 第一层，建模能力：把竹竿抽象成数轴上的区间，把“能否接上”抽象成区间是否相交。
• 第二层，贪心思想：排序后按顺序合并区间，维护当前可达的右边界。
• 第三层，代码基本功：排序、扫描、二分查找，用STL熟练实现。

很多考生栽在第一层。他们盯着“竹竿”两个字，试图模拟跳跃过程，用一堆条件判断去处理每一根竹竿的位置关系，结果把自己绕晕了。正确的做法恰恰相反——把竹竿全部画到数轴上，问题瞬间就清晰了。这也是我想在文章开头就强调的：信息学竞赛题，不是读题而是拆题。

1.3 为什么这道题区分度高

“接竹竿”的题面信息量不大，看起来也没什么吓人的术语，但区分度恰恰来自这里。基础一般的同学，能看懂题意，但想不到区间化；基础中等的同学，能想到区间化，却在边界条件上翻车；只有真正吃透区间合并本质的同学，才能又快又稳地拿下满分。这道题大概就是这种定位：它不考偏门算法，考的是你对经典算法的理解深度，以及考场上的细心程度。

2. 从题面到数学模型：把竹竿变成区间

2.1 题面关键条件还原

先把我记忆中的题面还原一下。大约是这样：地上水平放着若干根竹竿，给定每根竹竿的左端点坐标 x 和长度 len，那么这根竹竿就占据了数轴上 [x, x+len] 这么一段。你从某个位置 p 出发，沿数轴正方向前进。规则是这样的：遇到第一根竹竿时你必须跳上去，然后可以沿着竹竿走到它的右端点；如果下一根竹竿和当前竹竿在水平方向上有重合（包括端点正好相接），你就能直接跨过去继续走；如果中间出现了空隙，你掉到地上，行程就结束了。问的是：最远能到达哪个坐标。

不同版本可能在起点上略有出入，有的题目规定起点是 0，有的会给多个询问起点。但无论哪种版本，核心模型是一样的。只要你愿意多花两分钟把题面翻译成数学语言，整道题的复杂度瞬间就从“模拟跳跃”降成了“区间处理”。

2.2 区间化的三个关键推论

第一，竹竿的高度是没有用的。题面里竹竿横放在地面或同一水平面上，你的跳跃实际上是水平投影上的衔接。所以每根竹竿只需要关心它在 x 轴上占据的闭区间 [L, R] 就够了，完全不需要考虑“高度”“角度”这些干扰项。

第二，两根竹竿能“接上”的充要条件是：后一根竹竿的左端点不超过当前一根竹竿的右端点。也就是说区间 [L1, R1] 和 [L2, R2] 满足闭区间相交或相接的条件，即 L2 <= R1。不需要它们长度有多长，也不需要位置完全重合，只要存在一个 x 坐标，你站在前一根竹竿的右端或某个位置，能正好够到后一根竹竿的左端，就能继续前进。

第三，这个问题最终会变成一个“找连通块右边界”的问题。把所有竹竿按区间画在数轴上，互相之间有交叠的区间会连成一片。你不管从哪个点出发，只要你跳上了某一根竹竿，你能到达的最远位置，就是你所在的这一片连通区间的最右端点。如果你从地面出发，你会先遇到哪根竹竿？是那根左端点大于等于 p 的最靠左的竹竿，所以答案就是那根竹竿所在连通块的最右端点。

2.3 边界条件到底用 < 还是 <=

这是我在评论区看到讨论最多的问题，没有之一。两根竹竿端点恰好重合时，到底算不算“能接上”？

我的答案是：算。请你想象一个画面——第一根竹竿的右端点在坐标 5，第二根竹竿的左端点也在坐标 5。你沿第一根竹竿走到右端点，原地笔直站定，面前就是第二根竹竿的端点，你只需要迈一小步或者轻轻一跳就能过去。这个动作在物理上完全成立。所以判断条件一定是 L2 <= R1，而不是 L2 < R1。

这个细节在区间合并代码里就对应一行：if (a[i].L <= curR)。很多同学写成<，结果边界测试点一跑就错，非常可惜。闭区间就是闭区间，这种地方不是题目坑你，是你自己对“相接”这个概念的理解不够严谨。

3. 排序与区间合并：完整实现方案

3.1 总流程设计

整道题的做法分四步走：

1. 输入每根竹竿的左端点 x 和长度 len，计算右端点 R = x + len，存成区间。
2. 把所有区间按照左端点从小到大排序。如果左端点相同，就按右端点从小到大排，保证扫描时顺序稳定。
3. 线性扫描一遍，把互相接触的区间合并成一个个不相交的“连通块”。
4. 对每个询问起点 p，用二分查找定位到它所在的（或它前方第一个）连通块，输出这个连通块的最右端点。

如果你只有单起点询问，第4步可以直接在扫描过程中同步完成；但写成“分组+二分”的结构更通用，多询问也不用改。考场上面临时间压力的时候，我建议你直接用这个通用结构，因为它的逻辑线性单一，不容易在边界上出幺蛾子。

3.2 关键代码：区间合并

这道题我用最标准的 C++ 写法来实现，STL 的vector、sort、lower_bound都用上，代码量并不大：

#include <bits/stdc++.h> using namespace std; typedef long long ll; struct Node { ll L, R; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector<Node> a(n); for (int i = 0; i < n; i++) { ll x, len; cin >> x >> len; a[i] = {x, x + len}; } // 1. 按左端点排序 sort(a.begin(), a.end(), [](const Node& u, const Node& v) { if (u.L != v.L) return u.L < v.L; return u.R < v.R; }); // 2. 一次扫描，合并出互不相交的连通块 vector<Node> group; ll curL = a[0].L; ll curR = a[0].R; for (int i = 1; i < n; i++) { if (a[i].L <= curR) { // 与当前连通块有接触，扩展右边界 curR = max(curR, a[i].R); } else { // 出现空隙，当前连通块闭合 group.push_back({curL, curR}); curL = a[i].L; curR = a[i].R; } } group.push_back({curL, curR}); // 3. 提取所有连通块的左端点，用于二分 vector<ll> Ls; for (auto &g : group) Ls.push_back(g.L); // 4. 回答每个起点 while (q--) { ll p; cin >> p; int idx = lower_bound(Ls.begin(), Ls.end(), p) - Ls.begin(); ll ans; if (idx > 0 && group[idx - 1].R >= p) { // p 落在了前一个连通块的范围内，直接输出该块右端点 ans = group[idx - 1].R; } else if (idx < (int)group.size()) { // p 在空隙中或第一个块的左侧，跳上第一个遇到的块 ans = group[idx].R; } else { // p 右侧没有竹竿了 ans = p; } cout << ans << '\n'; } return 0; }

这里面最核心的是那个if (a[i].L <= curR)判断。它的含义就一句话：只要下一根竹竿的左端没有超过当前可达的右边界，我就能把右边界继续拓展。反之，如果a[i].L > curR，说明中间出现了货真价实的空隙，这一片连通块彻底结束，后面的竹竿无论怎么排列都不可能跨过这个空隙被接上来，因为它们的左端点只会更大不会更小。

curR = max(curR, a[i].R)这一步也值得多说一句。为什么不用curR = a[i].R？因为排序只保证了左端点有序，不保证右端点有序。可能出现前面一个长竹竿覆盖到 100，后面一根短竹竿左端点在 60、右端点在 70 的情况。如果直接赋值为 70，右边界反而缩小了，后面原本能接上的长竹竿就被错误地截断了。所以必须取两者的最大值。

3.3 复杂度分析

排序是 O(n log n)，线性扫描合并是 O(n)，每个询问做一次二分查找是 O(log n)。如果题意给的是单起点，整个算法就是 O(n log n)；如果给的是 q 个询问，整体是 O(n log n + q log n)。这个复杂度在 GESP 的题面数据范围下可以轻松跑过，哪怕是 n 取到 10^6 量级，排序 1e6 个数在现代评测机上也就是一瞬间的事。

相比之下，如果你真的去模拟每一根竹竿的跳跃路径，最坏情况要 O(n^2)，而且还要处理一堆无序的位置关系，代码写得越长越容易出错。这就是建模的价值：把问题形式化以后，一个教科书级的贪心扫描就能解决问题。

4. 回答查询的两种姿势

4.1 单起点：也可以直接扫描

如果题目只给你一个起点，你确实可以在扫描合并的同时计算出答案。基本流程是：先定位到第一根左端点大于等于 p 的竹竿，然后从它开始维护 curR，一边扫描一边扩展，直到遇到空隙为止。这样省掉分组后的二分查找，代码可能更短一点。

但我的建议是，不要为了省这一点代码而牺牲通用性。因为 GESP 八级的题目偶尔会把“单起点”改写成“多行询问”，你一上来看到q个询问，如果只写了单起点的扫描版本，就得现场重构。而分组+二分的版本，无论 q 是 1 还是 100000，都能原地不动地直接通过。

4.2 多起点：二分定位连通块

多起点的核心逻辑已经在上面代码里了，我再把它拆开揉碎讲一遍。假设我们已经把竹竿合并成了若干个互不相交的连通块group，每个块都有左端点 Ls[i] 和右端点 group[i].R：

• 情况一：p 落在某个连通块内部。这时你跳上该块后能一直走到块的最右端，答案是 group[i].R。
• 情况二：p 落在两个连通块之间的空隙。这时你从地面走到后方那个块（也就是第一个左端点大于等于 p 的块）的左端，跳上去，答案同样是那块的右端点。
• 情况三：p 在第一个连通块的左侧，答案就是第一个连通块的右端点。
• 情况四：p 的右侧没有任何连通块，也就是 p 大于所有竹竿的右端点，那么答案就是 p 本身（或者按题面要求的某个边界值）。

用lower_bound找到第一个Ls >= p的块下标 idx 之后，只需要检查前一个块的右端点是否大于等于 p，就能区分“p 在块内”还是“p 在空隙中”。这个检查极其关键，漏掉它，你的答案会在 p 恰好落进某个块时输出错误。

4.3 如何构造样例自测

不管是在考场上还是在平时练习，我都强烈建议你至少手算三组小数据再提交。这个习惯能帮你拦住一大半低级错误。就拿这道题来说，我通常会用下面几组：

第一组：一根竹竿

1 1 1 5 0

竹竿覆盖 [1,6]，起点 0，从地面走到 1 跳上去，最远到 6。答案 6。

第二组：两根竹竿有空隙

2 1 1 2 4 2 1

区间 [1,3] 和 [4,6]，起点 1。你从 1 上杆，到 3 时前面是空隙，结束。答案 3。

第三组：两根竹竿端点相接

2 1 1 2 3 2 1

区间 [1,3] 和 [3,5]，起点 1。端点重合，能接上，答案 5。

第四组：起点恰好在空隙里

2 1 1 2 5 2 3

区间 [1,3] 和 [5,7]，起点 3。从 3 向前走，遇到第一根竹竿是 [5,7]，跳上去，答案 7。

把这些样例跑一遍，你的二分逻辑和边界判断基本上就稳了。

5. 现场最容易踩的坑

5.1 坑一：忘记排序

这是我见过的最高频错误，没有之一。有人以为输入数据就是按顺序给的，直接不排序就扫描合并。这相当于赌命题人的数据善良，但竞赛数据从来不善良。不排序，你的“当前右边界”覆盖不到那些左端点更小却排在后面的区间，合并结果必然出错。记住，区间合并类问题的第一步永远是排序，这是铁律。

5.2 坑二：int 类型溢出

题目里 x 和 len 如果各是 10^9 量级，右端点 x+len 就是 2*10^9，已经超出 int 的表示范围了。我在网上看到不少同学用 int 存右端点，本地样例全过，提交后一两个测试点 WA，半天找不到原因。这种题一律用long long，不要有任何侥幸心理。排序、比较、答案输出，全部用long long，多打三个字母换来的是全场安心。

5.3 坑三：合并循环里提前 break

另一种常见错误是，扫描时遇到第一个空隙就 break，然后直接输出。这在单起点且只关心第一个连通块的场景下勉强成立，但如果你先整体分组、后面还要回答多组询问，提前 break 会丢掉后面的所有区间，导致分组不完整。正确做法是：遇到空隙就把当前块收尾，然后继续往后扫，而不是跳出整个循环。

5.4 坑四：更新右边界时忘了 max

前面分析过，curR = max(curR, a[i].R)和curR = a[i].R是完全不同的两件事。排序不能让右端点有序，所以你必须显式取最大值。这个错误特别隐蔽，因为小数据很难测出来，往往是在有“长区间包含短区间”的测试点才会暴露。

5.5 坑五：输入输出性能

很多考生平时用cin/cout从不开加速，到了大数据量的题就开始超时。GESP 八级的 n 通常不会特别大，但既然把ios::sync_with_stdio(false); cin.tie(nullptr);写上就能白捡性能，为什么不写？考场时间有限，不要在这种地方给自己添堵。

我把这些坑整理成一张速查表，方便你考前扫一眼：

6. 换个思路：并查集版本（选读）

6.1 为什么有时候想用并查集

区间合并的扫描法已经足够简洁了，那为什么还要提并查集？因为“连通性”这个词一旦出现，很多人的第一反应就是并查集。事实上，这道题确实可以套并查集：把所有互相接触的区间放到同一个集合里，最后找出起点所在集合的最右端点。

但我要提醒你：对一维区间来说，并查集是“杀鸡用牛刀”。区间在一维数轴上的连通性有一个非常好的性质——它是按顺序单向传播的，只要左端点有序，一次扫描就能合并完，根本不需要维护复杂的树结构和路径压缩。只有在处理更高维的连通问题，比如平面矩形连通、图上连通性，并查集才真正发挥威力。

6.2 并查集做法的思路大纲

如果你就是想写并查集版本，思路是这样的：先按左端点排序，用并查集把“和当前块有交叠”的区间连到同一个根上。具体实现要维护一个“当前最右端点”和“当前窗口”，保证每个区间只和前面的一个代表元合并，避免 O(n^2) 地枚举所有区间对。排序后可以做到接近 O(n log n) 的复杂度，但代码比扫描法复杂不少。

6.3 两种方案对比

我的看法是，考场写扫描法就够了，并查集可以作为思维拓展去理解。因为 GESP 八级考的是你在有限时间内稳定得分的能力，不是炫技。最稳的算法，就是最好的算法。

7. 同类题与备考建议

7.1 真题改编方向

“接竹竿”这个模型太经典了，命题人只要换层皮就能变成新题。我列举几个常见的改编方向，你在备考时如果能把它们都想明白，区间合并这一块就算彻底吃透了：

• 改成“最少需要多少根新竹竿才能从起点连通到终点”。这就变成了经典的区间覆盖问题，做法是排序后贪心选择能覆盖当前右端点的最右区间。
• 改成“给定一个目标点，判断能否从起点到达”。答案就是判断可达右端点是否大于等于目标点。
• 改成“求所有空隙中最长的那一段”。合并且分组完成后，扫描所有相邻组之间的空隙，取最大值。
• 改成“每个区间有权值，求从起点出发能获得的最大权值”。合并连通块的同时累加权值即可。

你会发现，这些变体全都建立在“区分区间、排序、合并、查询”这四个步骤之上。核心模型不变，换的只是外壳。

7.2 备考八级的刷题建议

GESP 八级的区间类问题，我建议你把三大经典题练透：区间合并、区间覆盖、区间选点。这三类题分别对应了三种不同的贪心策略，但它们有一个共同的起手式：把题面抽象成数轴上的区间，然后排序。我在备考阶段就是这么练的，先花两周把这三个题型的模板写到闭眼能敲的程度，再去做带场景包装的真题，会发现自己识别模型的速度快了很多。

另外一个很实用的建议是：每次读题后先不要急着敲键盘，拿笔画一下数轴。把竹竿画成线段，把起点标出来，眼睛看着图写代码，边界条件会清晰得多。有时候你在纸上画完图，代码的思路就已经自然而然地浮现出来了。

最后再分享一个小技巧

我实际做题时的习惯是，提交之前一定会把代码里所有和“右端点”有关的变量名检查一遍，确认每一处用的都是curR而不是a[i].R。这听起来很蠢，但人在考场高压状态下，最容易在自以为熟悉的地方犯低级错误。另一个习惯是写完后心里默念一遍那五个坑：排序了吗？long long 了吗？边界是 <= 吗？更新用 max 了吗？加速流开了吗？五句话念完，基本就能把低级的丢分点全部堵住。“接竹竿”这道题本身不难，难的是在有限时间内不犯任何一个低级错误。把区间合并这个模板吃透，你在八级考场上遇到它和它的所有变体，都能从容应对。