提到贪心算法很多入门的朋友第一次产生“我好像懂了但一做题就废”的感觉往往就是从这类区间问题开始的。比如信息学奥赛一本通里的 1423【例题2】种树题号看着普通但它背后的区间选点模型几乎贯穿了从普及组到提高组的整个区间贪心体系。这道题表面是种树本质上是“如何用最少的资源覆盖所有区间需求”——搞清楚它的贪心方向后面再遇到类似题思路会顺很多。先说题目本身一条路上有若干居民区段每个区段要求至少种 c 棵树区段之间会重叠同一棵树可以同时满足多个区段的要求问最少种多少棵树。我第一次带学生做这题时班里一半人第一反应是“按左端点排序从左往右种”结果一验证就翻车。这道题真正的核心不是盯着“从左往右”还是“从右往左”而是想明白你排序的目的是什么、种树的位置策略该服从什么。1. 题目到底在说什么种树问题背后的数学模型1.1 原题描述与输入输出格式我先按竞赛里常见的描述方式把题目复述一遍。假设有一段长度为 n 的道路路上有 m 个居民第 i 个居民希望在闭区间 [l, r] 这一段道路内至少种 c 棵树。一个位置只能种一棵树但如果这棵树同时落在多个居民要求的区间内它就可以同时满足多个需求。现在求在满足所有居民要求的前提下最少需要种多少棵树。输入通常是这样的格式n m l1 r1 c1 l2 r2 c2 ... lm rm cm注意原题里 n 表示道路总长即位置编号范围是 1 到 n。但在实际做题时你会发现n 这个值有时候用不上——只要你种树的位置始终落在居民给出的区间内并且数组开得足够大n 不会影响最终答案。不过建议还是把它读进来做一次越界检查后面排查问题会省很多事。输出就是一个数字最少种树数量。1.2 为什么这是贪心算法而不是简单的模拟有的初学者会想这题直接模拟不就行了每个区间要求多少棵我就往里种多少棵统计一下总数。但问题在于一棵树种在什么位置决定了它能“顺带满足”多少个后续区间。如果你在每个区间里随便找个位置种很可能出现这种情况后面一个区间的需求本来可以被前面种的树覆盖掉但因为位置差了一点不得不额外种新树总数就变大了。换句话说种树决策之间存在“相互影响”你需要通过合理安排位置来最大化每棵树的利用价值。这类问题的最优解不能靠局部顺序模拟得到必须通过贪心策略来构造。这里引入一个经典模型区间选点问题。把每个居民要求的区间看成一个需求片段每棵树看成一个“点”。目标是选尽量少的点使得每个区间内至少包含 c 个点。这就是“最小点覆盖区间”的变形也是贪心算法里最典型的几类区间问题之一。1.3 一道题串起三个经典模型种树这题的价值在于它一个题目串起了三个在竞赛里反复出现的模型模型一单个区间内至少选 k 个点求全局最少点数——本题的直接形式。模型二活动安排 / 区间调度——同样要按右端点排序但贪心目标从“覆盖所有区间”变成“选尽量多互不重叠的区间”。模型三任务调度 / 线段覆盖——本质上是模型一的扩展区间之间可能有优先级或附加权值。所以别觉得 1423 只是一道简单的提高篇例题。把这一题吃透相当于把区间贪心的一大半套路都掌握了。后面遇到“选点覆盖”“安装摄像头”“安排路灯”这类题目你会发现它们的内核跟种树完全一样只是换了个故事背景。2. 贪心策略的核心推导为什么必须按右端点排序2.1 先想清楚“占便宜”的方向我在实际讲课的时候喜欢先让学生回答一个问题如果你是一棵“聪明的树”你会选择种在哪个位置注意这里不是站在人的角度去规划而是站在“树”的角度思考——一景点在哪才能被尽量多的区间覆盖到答案其实非常直观靠右的位置比靠左的位置更有可能被后续区间覆盖。因为当我们把区间按某种顺序处理时后续出现的区间右端点不会比当前区间的右端点更靠左。如果你把树尽量种在当前区间靠右的位置那么这些树落入后续区间的概率更高。反之如果种在靠左的位置后续区间的左端点稍微往右一偏这棵树就彻底浪费了。这就是种树问题贪心策略的第一条原则按右端点从小到大排序然后从右往左种树。2.2 数学化表述与严格化证明光有直觉不够竞赛里你最好还能写出让人信服的论证。我们假设已经按右端点升序排序当前处理到区间 [l, r]它还需要若干棵树。这时已处理完的区间的右端点都不大于 r因此它们种下的树如果落在当前区间内一定落在 [l, r] 内。接下来证明一个关键结论补种树时优先种在 r、r-1、r-2……这些靠右的空位上一定不比种在别处差。考虑两种方案方案 A 在当前区间补种时选择最靠右的空位方案 B 选择了一个更靠左的位置。如果后续某个区间需要覆盖某棵树而这个区间的左端点大于“更靠左的位置”那么方案 B 中这棵树就失去了作用但方案 A 的树因为更靠右仍然可能被覆盖到。换句话说方案 A 的每一棵树在满足当前区间需求的同时还保有最大的“覆盖潜力”。所以方案 A 不会比方案 B 差贪心成立。这个证明思路可以概括为当前决策不影响已经处理完的区间只可能对未来的区间产生正面影响因此选择对未来最有利的方案就是最优的。2.3 排序细节右端点相同怎么办排序时还有一个经常被忽略的细节如果两个区间右端点相同谁在前谁在后答案是排序时右端点为主关键字升序左端点可以任意或者说升序降序都不影响正确性。但为了稳定性我习惯写成右端点升序如果右端点相同左端点升序。这样处理区间时范围更小的区间会先被处理相当于先用“短区间”约束住种树位置后面的大区间再顺带满足逻辑上更顺。bool cmp(const Seg a, const Seg b) { if (a.r ! b.r) return a.r b.r; return a.l b.l; }这里还有个容易踩的小坑如果你在排序时没处理左端点某些数据下程序也能跑出正确答案容易让人产生“无所谓”的错觉。实际上右端点相同的情况下左端点顺序虽然不影响答案但会影响你中间检查的命中率间接影响效率。竞赛里数据量大时别在这种细节上省事。3. 完整代码实现与关键步骤拆解3.1 数据结构设计代码层面其实很简单但结构设计要清晰否则排查问题的时候会非常痛苦。我通常这样定义#include bits/stdc.h using namespace std; struct Seg { int l, r, c; // 左端点、右端点、需要的棵数 }; const int MAXN 30005; // 根据题目数据范围调整 bool used[MAXN]; // 标记某个位置是否已经种了树 Seg segs[MAXN]; int n, m;used 数组是整个算法里唯一的状态载体。这里有一个隐含约束一个位置只能种一棵树但一棵树可以被多个区间重复计数。所以检查区间内已有树的个数时就是数 used 数组在该区间内的 true 数量。数组大小方面我习惯开到数据范围上限再加一点余量养成习惯后能避免不少越界问题。如果题目里 n 给到了 30000MAXN 就开 30005 甚至 30010不要卡着边界开。3.2 主流程代码int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; for (int i 0; i m; i) { cin segs[i].l segs[i].r segs[i].c; } sort(segs, segs m, cmp); int ans 0; for (int i 0; i m; i) { int need segs[i].c; // 统计当前区间内已经种了多少棵 for (int p segs[i].l; p segs[i].r; p) { if (used[p]) need--; } // 如果不够从右往左补种 for (int p segs[i].r; p segs[i].l need 0; p--) { if (!used[p]) { used[p] true; need--; ans; } } } cout ans endl; return 0; }这个过程的核心逻辑只有两步先数已有的再补缺的。数已有的这一步很多人会写错——不是在第一次循环里往上累加而是用“需要数”减去“已有数”或者像我这样直接把 need 递减。两种写法本质一样但递减写法的可读性更好因为你一眼能看出 need 表示的是“还缺多少棵”。3.3 验证一下这组数据为了验证算法我构造一组有代表性的数据8 4 1 3 2 3 6 2 2 4 2 7 8 1按右端点排序后的顺序是[1, 3] 需要 2 棵在位置 3、2 种下ans 变为 2。[2, 4] 需要 2 棵数一下区间内已有位置 2、3两棵刚好满足不补种。[3, 6] 需要 2 棵位置 3 已有 1 棵还缺 1 棵从 6 往 3 找位置 6 空闲种下ans 变为 3。[7, 8] 需要 1 棵位置 8 空闲种下ans 变为 4。最终答案是 4。你可以试着换一种策略比如每个区间独立种树成本肯定更高。这组数据里有重叠区间的覆盖问题也有完全独立的区间能很好地检验算法对两种情况的处理能力。3.4 时间复杂度分析排序复杂度是 O(m log m)。处理每个区间时数已有树和补种都要扫描区间长度最坏情况下区间长度是 O(n)所以总复杂度是 O(m log m m n)。这个复杂度在 n 不大时完全够用。但如果 n 很大比如到了 10 的 6 次方m 也到了 10 的 5 次方m n 就会达到 10 的 11 次方直接超时。这时可以考虑用并查集优化“找下一个空闲位置”的过程把补种操作的复杂度降到近乎 O(1)。我在后面的变体部分会再展开。4. 从入门到不掉坑常见错误与排查技巧4.1 错误一按左端点排序这是最经典的错误基本每个初学者都犯过。要是按左端点升序排序然后同样从右往左补种会出现什么问题构造一个反例[1, 10] 需要 1 棵 [2, 9] 需要 1 棵 [3, 8] 需要 1 棵按左端点排序后是 [1,10]、[2,9]、[3,8]。处理 [1,10] 时按贪心策略从右往左种会种在位置 10。到 [2,9] 时位置 10 不在区间内区间内一棵树都没有不得不种一棵在 9。再到 [3,8] 时10 和 9 都不在 [3,8] 内又得种一棵在 8。最终答案是 3但正确答案其实是 1——只需要在位置 8 种一棵三个区间全部满足。按右端点排序就没这个问题。排序后是 [3,8]、[2,9]、[1,10]先处理小区间种在 8后面两个大区间自动覆盖。关键原因在于区间越靠后处理右端点越“靠右”那你之前种在右侧的树就越有可能被覆盖到。按左端点排序完全破坏了这一性质。4.2 错误二补种起点选错有些同学知道要按右端点排序但补种的时候习惯从左往右找空位结果也一样翻车。比如区间 [1, 5] 需要 1 棵后续有一个区间 [4, 6] 也需要 1 棵。处理 [1,5] 时如果从左往右种会种在位置 1后面 [4,6] 里一棵都没有又得种一棵。如果从右往左种种在 5后面的区间直接满足。这里的判断标准只有一个在当前区间内种树越靠右越可能被后续区间使用。4.3 错误三区间包含时直接累加还有一类错误出现在统计已有树数量时。有的同学想省事认为前面已经处理过的区间里种的树肯定都在当前区间里所以直接把上次的树数累加。这在区间完全包含的情况下会出问题。比如前面处理的区间是 [1, 10]树全部种在位置 1、2、3 附近当前区间是 [5, 8]。你累加时以为有 3 棵树在里面实际上一棵都没有。所以统计已有树这件事必须老老实实扫描当前区间不能靠记忆。4.4 常见问题速查表症状可能原因修复方式答案偏大按左端点排序改为按右端点升序答案偏大补种时从左往右找空位改为从 r 往 l 找答案偏小统计已有树时只看部分位置完整遍历 [l, r]运行越界数组开小了按数据上限加余量答案不稳定排序时右端点相同处理不一致追加左端点升序规则这里的每一条都是从实际调试中总结出来的。特别是“答案偏大”这一类很多时候不是算法思路错了而是排序方向或者补种方向写反了。我建议你在本地验证时除了用题目样例一定要自己构造几组重叠多、边界紧的数据跑一遍可以快速暴露问题。5. 变体与进阶种树问题的三种升级玩法5.1 变体一每个区间只需要 1 棵树的最小点覆盖这是种树问题最简单的版本每个区间需求数都是 1求覆盖所有区间的最少点数量。做法跟种树完全相同按右端点排序每次检查当前区间是否已经被覆盖如果没有就在右端点种一棵。这个模型在实际场景里很常见比如路上安装路灯覆盖若干段道路、给若干个活动时间段安排一名摄影师等。你能一眼识别出“这是区间选点”基本上代码十分钟内就能写完。5.2 变体二区间调度问题——同样是排序目标完全不同区间调度问题是和种树长得最像、但解题方向又最容易混淆的问题。给定若干活动区间每个区间有开始时间和结束时间问最多能安排多少个互不重叠的活动。这个问题当然也按右端点排序但贪心策略是“每次选择结束时间最早且与已选活动不冲突的活动”。它跟种树的区别在于种树是“越大范围越容易覆盖所以尽量利用右端点”调度是“结束越早越可能为后面留出空间”。两者放一起对比着学效果特别好排序方向相同但决策策略不同。建议你把这几个题放在一起刷种树、活动安排、线段覆盖反复体会“右端点排序”在不同问题里如何链接到不同的后续决策。5.3 变体三大数据范围下的优化——并查集加速找空位回到前面的复杂度问题。如果道路长度 n 达到 10 的 6 次方区间数量 m 达到 10 的 5 次方逐个扫描空闲位置就会超时。这时需要用并查集维护“下一个未种树的位置”。具体思路是初始化每个位置的父亲指向自己。当一个位置被种了树就把它的父亲指向下一个位置。补种时不断查找区间右端点的“前驱空位”一步就能跳到下一个空闲位置。整个过程类似路径压缩均摊复杂度接近 O(1)。int findNext(int x) { if (x ! fa[x]) fa[x] findNext(fa[x]); return fa[x]; }这个优化在竞赛里非常实用尤其是搭配二维树状数组处理复杂覆盖问题时常常能起到画龙点睛的作用。建议你先把普通版本写熟练再考虑优化不要一上来就套并查集反而容易把自己绕晕。6. 写在最后的经验之谈带了几届学生之后我最大的体会是区间贪心类题目翻车基本都翻在“排序方向”和“补种方向”这两件事上。很多同学不是不理解贪心思想而是没有把“当前决策是否会影响未来收益”想透彻就开始写代码。种树这道题好就好在它用最朴素的故事强迫你思考这个问题——树的位置靠左还是靠右直接决定了后续区间能不能“占便宜”。最后再分享一个我实践中的小技巧拿到任何区间贪心题先别急着写代码在草稿纸上画一条数轴把区间画出来再模拟两轮“如果你是那棵树/那个点你愿意待在哪”。这一步能帮你避开大部分策略性错误。种树这道题要是吃透了后面再看到各种“装监控”“排路灯”“选基站”的题目你其实可以直接把代码模板搬过去改个名字就能交卷。