企业官网建设流程全解析

下午答疑的时候，有个同学指着白板上的区间调度题问我：“教练，为什么每次选结束时间最早的，就一定是对的？万一选了它，后面反而亏了呢？”这个问题几乎是每一届寒假集训都会出现的经典一问，也是贪心专题里最值得停下来想清楚的地方。

这篇内容就是我在寒假集训第六课“贪心”中的完整讲法，包括贪心算法的核心思想、几类高频模型的推导过程、代码实现上的细节坑，以及我带集训时总结出来的一套训练和复盘方法。不管你是刚开始接触算法的竞赛初学者，还是在准备面试算法题、考研机试的同学，这篇内容都可以直接作为你贪心专题的入门和进阶参考。

1. 贪心算法的核心思想：为什么“局部最优”能通向“全局最优”

1.1 贪心到底是什么

贪心算法（Greedy Algorithm）的想法一句话就能说完：在每一步决策的时候，都选择当前看起来最好的那个选项，并且不回头、不后悔，一路走到最后，希望最终得到的整体结果也是最好的。

这个策略的本质是“短视”。它不像动态规划那样，会去记录所有可能的子问题状态，再从中挑一个全局最优的解。贪心算法的每一步都是独立做决定，一旦选了就不改。所以，它看起来是一种很“冒险”的策略——你在每一步都押注当前最优就是全局最优。

那为什么有时候这种“短视”的策略能成功？关键在于问题本身的结构。如果一个优化问题具备两个性质，贪心就是安全的：

• 贪心选择性质：每一步的局部最优选择，最终能被包含在某个全局最优解里。换句话说，当前这一步的选择不会堵死通向最优解的路。
• 最优子结构：做完一次贪心选择之后，剩下问题的最优解，仍然可以由“同样的贪心策略”递归地构造出来。子问题的最优解组合起来，就是原问题的最优解。

这两个性质合在一起，才保证了“一路选下去”能得到正确答案。如果只满足其中一个，贪心就很可能翻车。

1.2 为什么很多人觉得贪心“不严谨”

我在集训第一天就明确跟学生说：贪心这个专题，最难的其实不是“想到贪心”，而是“证明贪心是对的”。

现实是，大部分人在做题时都是先靠直觉猜一个策略，然后写代码去提交，如果过了就认为没问题，如果没过就换一个策略再试。这种“试错式”的学习方式应付模板题还行，但一旦题目设置了一个隐藏的反例，就会卡到怀疑人生。

举个例子：假设有硬币面额 1元、3元、4元，要凑出 6元。贪心策略是优先用最大面额，那么会取 4 + 1 + 1，一共3枚。但最优解明明是 3 + 3，只要2枚。这个例子说明，直观上“先用大面额”听起来很合理，但在这个面额组合下它就不成立了。

所以，贪心算法的学习必须分成两条线：一条线是积累“贪心模型”，看到题能识别出它属于哪一类；另一条线是掌握“正确性证明”的工具，至少能说服自己这个策略不是碰巧过的。这两条线，我都会在这个专题里带着大家一条一条捋清楚。

2. 经典贪心模型的拆解与证明方法

2.1 区间调度模型：按结束时间排序的奥秘

区间调度类问题，是贪心算法里最典型、也最容易被拿出来考察的一类。它的核心场景是：有一堆活动，每个活动有开始时间和结束时间，同一时刻只能参加一个活动，问最多能参加多少个完整的活动。

标准的贪心策略是：把所有活动按结束时间升序排序，然后从左到右扫描，只要能选就选，每次选完把当前时间更新为这个活动的结束时间。

很多同学第一反应是“按开始时间排序”或者“按持续时间排序”，这两种策略都能举出反例。按开始时间排序的问题在于，一个开始很早的活动可能持续时间很长，选它会导致后面好几个活动都排不进去；按持续时间排序也有问题，一个很短的活动可能横跨在两个关键时间点中间，反而挡住了更多活动。

为什么按结束时间排序一定对？这里用到的是“交换论证法”的思路：

假设存在一个最优解，它的第一个活动不是所有活动中结束时间最早的，那么我用结束时间最早的那个活动去替换最优解的第一个活动。最早结束的活动，它的结束时间一定不晚于最优解第一个活动的结束时间，所以它不会跟后面的任何活动冲突。替换之后，解的活动数量不变，仍然是一个合法的最优解。接下来，把被替换掉的那个活动从问题里删掉，继续对剩余活动做同样的操作，反复替换之后就能得到一个完全由贪心策略构造出来的最优解。

这个证明思路是贪心算法最重要的数学工具之一。遇到一个猜想的贪心策略，很多情况下都可以用“假设最优解第一个元素不是我选的这个，我把它换掉，不变得更差”这种方法来验证。

2.2 排队接水模型：短作业优先的背后是交换代价

另一个必讲模型是排队问题。场景是：有 n 个人排队接水，第 i 个人接水需要 t_i 的时间，每个人的等待时间是从他开始排队到接完水为止，求所有人等待时间总和的最小值。

贪心策略很简单：按接水时间从短到长排队，也就是“短作业优先”。

这个策略直观上很容易理解：让接水快的人先接，后面排队的人等的时间就少。但要用数学方式说明白，还是要交换论证。假设队伍里有两个相邻的人 i 和 j，接水时间分别为 t_i 和 t_j，并且 t_i > t_j，也就是慢的排在快的前面。其他人的等待时间不受这两人相对顺序的影响，我们只需要比较这两个人内部产生的等待时间差异。

如果 i 排在 j 前面，那么两人贡献的等待时间是：

• i 自己在等待 t_i（从开始到接完）
• j 等待了 t_i + t_j

合计是 2t_i + t_j。

如果交换顺序，让 j 在前面、i 在后面，合计是 2t_j + t_i。

两者相减：(2t_i + t_j) - (2t_j + t_i) = t_i - t_j > 0。

说明慢的在前面的方案，两人的等待总时间更大。所以只要存在相邻逆序，交换之后一定更优。不断交换下去，最终一定形成一个按时间升序排列的队伍。这就是“相邻交换法”的标准应用。

这个模型还有一种变形是“每个任务有完成截止时间，完成一个任务获得固定收益，如何最大化收益”。这种题的贪心策略通常是把任务按截止时间排序，然后用一个小根堆维护已选任务的耗时，遇到超时的情况就淘汰掉耗时最长的任务。核心思想其实还是“保住单位时间收益最大”的思路，只是在数据结构上多了个优先级队列。

2.3 背包问题的边界：为什么部分背包能用贪心，0-1背包不行

背包问题是我在讲贪心时一定会拿出来做对比的案例。同样是背包，同样是容量限制，同样是拿物品放进去求最大价值，部分背包和0-1背包的命运完全不同。

部分背包的意思是物品可以切割，拿一部分也可以。这种情况贪心策略是：按单位重量的价值（价值/重量）从高到低排序，优先装单位价值高的物品，能装多少装多少。为什么对？因为每单位重量的“性价比”是独立的，你每装入一份物品，消耗的容量换来的收益应该尽量高，这就是典型的贪心选择性质。你可以把它理解成：同样一公斤空间，装价值高的那个碎块一定不会比装价值低的碎块差。

0-1背包则完全不同，每个物品只能整件拿或者不拿。这时候“性价比优先”的策略会失效。经典的例子是：背包容量 10，物品 A 重量 7 价值 9（性价比约1.29），物品 B 重量 5 价值 5（性价比1），物品 C 重量 5 价值 5（性价比1）。按性价比排序会先装 A，剩下容量 3 装不了任何东西，总价值 9。但最优解是装 B 和 C，总价值 10。

这就是0-1背包需要用动态规划的原因：物品不能拆分，装入一个物品会占掉一块容量，这个“占位”的代价必须通过状态转移来权衡，不能简单地按单价贪心。理解了这两者的边界，你就不会在0-1背包的题里冲动地写贪心了。

2.4 哈夫曼编码与合并果子：小根堆的典型战场

合并果子是一道树形结构的经典贪心题。题目场景是：有很多堆果子，每次只能合并相邻的两堆，合并的代价等于两堆重量之和，问最终合成一堆的最小总代价。

贪心策略是：每次选当前重量最小的两堆合并。这个策略的正确性可以借助“最优二叉树”来理解：把所有合并过程画成一棵二叉树，每个叶子是一堆原始果子，内部节点的权值是两个孩子权值之和。总代价等于所有内部节点权值之和，也等于每个叶子的权值乘它的深度。要让这个值最小，权重大的叶子应该尽量放在深度小的地方，权重小的叶子可以放在更深的位置。每次合并最小的两堆，本质上就是在逐步构建这样一棵“重叶子靠上、轻叶子靠下”的最优二叉树。

实现上，最自然的数据结构是优先队列（堆）。每次从堆里弹出两个最小值，合并后把新值压回堆里，重复 n-1 次。这里要特别注意：很多语言的默认优先队列是“大根堆”，也就是每次弹出最大值，如果你不改变比较规则就直接用，程序会错得完全看不出来——因为样例数据往往很小，堆的性质在大数据下才会显露出问题。这个问题我后面会在“踩坑”部分专门讲。

3. 关键排序策略与代码实现细节

3.1 排序比较器的写法：C++ 与 Python 实战对比

贪心算法里，排序是最高频的操作。排序排得好不好、比较器写得对不对，直接决定整个题目的正确性和效率。我见过太多学生在自定义排序规则上翻车，所以这部分我写得很细。

先看 C++。标准库 sort 的第三个参数可以传一个比较规则。比较规则必须满足“严格弱序”，简单说就是：如果两个元素相等，比较函数必须返回 false，不能返回 true。

#include <bits/stdc++.h> using namespace std; struct Activity { int start, end; }; int main() { int n; cin >> n; vector<Activity> acts(n); for (int i = 0; i < n; i++) { cin >> acts[i].start >> acts[i].end; } // 按结束时间升序排序 sort(acts.begin(), acts.end(), [](const Activity &a, const Activity &b) { return a.end < b.end; }); int ans = 0; int lastEnd = 0; for (auto &act : acts) { if (act.start >= lastEnd) { ans++; lastEnd = act.end; } } cout << ans << endl; return 0; }

有几个细节要注意。第一，lambda 比较器里我写的是<，不是<=。写成<=在 sort 里可能导致未定义行为，因为严格弱序要求“相等时返回 false”。第二，排序的稳定性：如果结束时间相同，按结束时间排序就已经足够，不需要再按开始时间做二级排序，因为它们的结束时间一样，选哪一个不影响后续可用时间。

再看 Python。Python 的排序函数强大且直观，但性能上对比较大的 n 会稍微慢一些，这在竞赛中要注意常数优化。

import sys n = int(sys.stdin.readline()) activities = [] for _ in range(n): s, t = map(int, sys.stdin.readline().split()) activities.append((s, t)) activities.sort(key=lambda x: x[1]) ans = 0 last_end = 0 for start, end in activities: if start >= last_end: ans += 1 last_end = end print(ans)

Python 的sort是稳定的，而且支持 key 函数，直接指定x[1]就能按结束时间排。如果比较规则复杂到要用两个字段，可以返回元组，比如key=lambda x: (x[1], x[0])。注意元组比较的顺序：先比第一个元素，再比第二个元素。

3.2 合并果子的最小堆实现：避免默认大根堆的陷阱

合并果子的堆实现里，C++ 的 priority_queue 默认是大根堆。很多第一次写这题的同学直接写priority_queue<int> pq;，然后连续两次弹出堆顶，结果每次弹出的都是最大的一堆，合并出来的总代价会大得离谱，而且在小样例上不一定看得出来。

正确的写法是使用小根堆：

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; priority_queue<int, vector<int>, greater<int>> pq; for (int i = 0; i < n; i++) { int x; cin >> x; pq.push(x); } long long ans = 0; while (pq.size() > 1) { int a = pq.top(); pq.pop(); int b = pq.top(); pq.pop(); int s = a + b; ans += s; pq.push(s); } cout << ans << endl; return 0; }

我标了long long ans，因为 n 最大可以到 1e5、每个值也可以很大时，总代价的增长是平方级别甚至更高的，用 int 存会溢出。这个“累加结果开 long long”的习惯，值得在所有贪心题目里养成。

Python 的实现里，heapq默认就是小根堆，所以反而更贴合直觉：

import heapq n = int(input()) a = list(map(int, input().split())) heapq.heapify(a) ans = 0 while len(a) > 1: x = heapq.heappop(a) y = heapq.heappop(a) s = x + y ans += s heapq.heappush(a, s) print(ans)

3.3 区间覆盖与区间选点的排序变体

区间调度讲的是“最多能选几个活动”，但同一个区间模型搬到“区间覆盖”和“区间选点”上时，排序方向和方法会变。

区间覆盖问题的标准场景是：给定一个目标区间 [L, R]，给你一堆区间，问最少选几个区间能完整覆盖 [L, R]。这里贪心策略变成：先把区间按左端点升序排序，然后从当前覆盖位置 cur 开始，在所有左端点小于等于 cur 的区间里，选右端点最大的那个，把 cur 更新为这个右端点，直到覆盖到 R。

为什么这次不按右端点排序了？因为区间覆盖的目标是“往右推进”，每一步要尽可能多覆盖一些未知区域。你关注的是“给定左边界，哪个区间能延伸得最远”，所以右端点变成了被比较的属性。

区间选点问题（求最少点让每个区间都至少包含一个点）则又是另一种策略：按右端点升序排序，每次选择当前区间右端点作为点，然后跳过所有已经被这个点覆盖的区间。这个策略本质上和活动选择非常相似，只是选出来的“活动结束时间”变成了“点的位置”。

三种模型放在一起看，它们共享同一个底层逻辑：每个贪心决策都要在某个“轴”上进行排序，排序的轴就是问题中的关键约束。关键在于判断，哪一维约束是决策时真正需要优先满足的。想通了这一点，遇到变形题时就不会慌。

4. 实战中踩过的坑：贪心失效案例与排查思路

4.1 反例意识：为什么会“看起来对但 WA”

集训进度过半时，我统计学生提交记录发现，贪心专题的第一次提交通过率是所有专题里偏低的。原因不是代码写得不好，而是大部分人在策略选择阶段就错了。

最常见的失败模式是：拿到题，觉得“某策略很自然”，不验证、不构造反例，直接写完提交，然后被测试数据打脸。这里我特别想强调一个习惯：在写代码之前，先尝试构造一个反例来攻击自己的策略。如果构造不出来，再开始写代码。这个“攻击自己”的过程只需要两三分钟，但能帮你规避掉一半以上的 WA。

以排队接水为例，如果你脑子里冒出“按时间从长到短排”，你可以在草稿纸上列 3 个人，时间分别为 1、2、100，算一算两种排法的等待总时间，很快就能发现长作业优先明显更差。很多反例只需要三五组数据就能构造出来，关键是你要有主动构造的意识，而不是写完代码直接交。

4.2 数据类型与边界条件的典型翻车

贪心代码的常见翻车点，我总结成了一张速查表，训练时可以直接对照排查。

浮点数精度这点值得展开说一下。部分背包要按“价值/重量”排序时，很多学生的第一反应是直接算个 double 存下来再排。但如果两个物品单价非常接近，浮点数误差可能导致排序结果和数学上的大小关系不一致。更稳的做法是用交叉相乘比较：a.val / a.weight > b.val / b.weight 等价于 a.val * b.weight > b.val * a.weight，全部用整数运算，既快又准。

4.3 用“对拍”验证贪心策略：从入门到熟练

在所有排查手段里，对拍是压箱底的绝招。对拍的意思很简单：写两份代码，一份是你要验证的贪心解法，一份是用暴力枚举或搜索写的正确答案（代码可以慢，但必须绝对正确），然后用随机数据同时跑两份程序，对比输出是否一致。如果随机跑了几千组数据结果都一样，你这个贪心策略的正确性就非常可信了。

我强烈建议每个学算法的同学都在本地存一套万能对拍脚本。流程是这样的：

1. 写一个数据生成器，随机生成符合题目条件的小规模数据（数据量要小，保证暴力程序能快速跑完）。
2. 写一个暴力程序，用枚举、递归或者朴素动态规划求正确答案。
3. 写你要验证的贪心程序。
4. 写一个循环脚本，每次生成新数据，分别跑两个程序，diff 它们的输出。输出不一致就停下来，把当前这组数据打印出来。

这个脚本写起来只要十几分钟，但它在整个集训期间的做题效率提升是巨大的。遇到一个新题，先用对拍验证一下你的贪心猜想，确认正确后再去调代码细节，能省下大量“提交-失败-思考”的循环时间。

在集训中我也发现，很多学生在比赛环境下不敢用对拍，担心浪费时间。实际上，一道贪心题如果策略本身没想清楚，调代码提交的轮次往往远超十分钟。相比之下，对拍的几分钟投入非常划算。我个人的习惯是：贪心猜想的对拍验证控制在五分钟内，如果五分钟后策略还没被推翻，我就会收回写代码。

5. 寒假集训的练习路线与复盘建议

5.1 从模板题到变形题的三个台阶

贪心这个专题，最怕的就是学生刷了一堆题，但只是在重复“排序+扫描”的固定套路。所以我在安排集训作业时，刻意把题目分成了三个台阶。

第一台阶是模板题，目标是把模型和代码流程刻进肌肉记忆。活动安排、排队接水、合并果子这三道题，我要求学生做到闭卷、快速、一次通过。第二台阶是变形题，例如把“最多活动数”改成“最少教室数”、把“单机调度”改成“多机调度”、把“区间覆盖”改成“覆盖所有点最少区间数”。这些题看起来是新的，但底层模型还是那些，只是需要你多做一步转换。第三台阶是综合题，通常结合二分答案、差分数组等技巧。比如“给定一个数组，用最少的操作次数让所有数满足某个条件”这类题，常见的思路是先二分答案，然后用贪心去 check 这个答案是否可行。

训练贪心，千万别陷入“题海战术”的效率陷阱。我宁可你一天只吃透三道题，把每道题的贪心证明写出来，也比一天刷二十道只交代码不思考要强。

5.2 复盘方法：错误分类与记录

每次训练结束后，我都会让学生做一个动作：把今天的错误分成三类，并记录下来。第一类是策略错误，也就是贪心猜想本身不成立，这类错误体现的是模型识别不熟练、反例意识不够。第二类是代码实现错误，比如排序比较器写错、堆的方向用反，这类错误要靠对照速查表逐项检查。第三类是数据范围错误，比如漏了 long long，这类错误要有意识地做完题就检查变量的取值范围。

记录下来之后，每隔三天翻一次，你会发现很多错误其实是反复出现的。集训到后半程，学生的反馈里普遍提到“同类错误越来越少了”，这正是复盘最大的价值。

5.3 每天的训练节奏建议

寒假集训的节奏比较紧凑，贪心专题通常安排三到四天。我建议的每日节奏是：上午用半小时复习前一天的模板题，然后花两小时做新题，下午集中对拍验证，晚上整理错题和证明思路。

特别说一下“证明思路”这个环节。很多同学觉得证明是数学家的事，写代码不需要。但在集训中我观察到，凡是能把“为什么贪心是对的”写清楚的同学，遇到变形题的通过率明显更高。因为写证明的过程中，你必须真正理解题目的约束条件是什么、排序的轴为什么是那个维度，这种理解会直接迁移到新题上。哪怕只写三行字的证明，也比完全靠猜要强得多。

最后分享一个小技巧。我在集训中反复跟学生说：贪心算法不只是一个算法知识点，它更是一种“先验证、后行动”的思维方式。你在做题时养成“先构造反例攻击自己，再写代码”的习惯，不仅算法题能用，生活中的很多决策也能用。每次看到一个看起来很美的方案，先问一句：有没有特殊情况会让它失效？多问这么一句，能帮你避免大多数想当然的错误。

这份寒假集训的贪心专题笔记，是我连续几届带学生积累下来的内容。如果你正在刷贪心算法题，建议从区间调度和排队接水两个模型入手，先把代码流程跑顺，再尝试对拍验证自己的策略。贪心的题目千变万化，但核心模型就那几个，练熟之后，你看到新题时会发现，很多所谓的新题，不过是老模型换了一件衣服。