企业官网建设流程全解析

提到贪心算法，很多入门的朋友第一次产生“我好像懂了但一做题就废”的感觉，往往就是从这类区间问题开始的。比如信息学奥赛一本通里的 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 给到了 30000，MAXN 就开 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 常见问题速查表

这里的每一条，都是从实际调试中总结出来的。特别是“答案偏大”这一类，很多时候不是算法思路错了，而是排序方向或者补种方向写反了。我建议你在本地验证时，除了用题目样例，一定要自己构造几组重叠多、边界紧的数据跑一遍，可以快速暴露问题。

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. 写在最后的经验之谈

带了几届学生之后，我最大的体会是：区间贪心类题目，翻车基本都翻在“排序方向”和“补种方向”这两件事上。很多同学不是不理解贪心思想，而是没有把“当前决策是否会影响未来收益”想透彻就开始写代码。种树这道题好就好在，它用最朴素的故事强迫你思考这个问题——树的位置靠左还是靠右，直接决定了后续区间能不能“占便宜”。

最后再分享一个我实践中的小技巧：拿到任何区间贪心题，先别急着写代码，在草稿纸上画一条数轴，把区间画出来，再模拟两轮“如果你是那棵树/那个点，你愿意待在哪”。这一步能帮你避开大部分策略性错误。种树这道题要是吃透了，后面再看到各种“装监控”“排路灯”“选基站”的题目，你其实可以直接把代码模板搬过去，改个名字就能交卷。