贪心算法全解：从活动选择到拟阵理论的竞赛实战

贪心算法是竞赛中最常用的算法思想之一，看似简单，实则对思维要求很高。

一、贪心算法核心思想
每一步选择当前看起来最优的方案，期望最终得到全局最优解。

贪心成立的条件（之一）：

• 问题具有最优子结构


• 贪心选择性质：局部最优能推出全局最优

1. 活动选择问题：按结束时间排序


2. 合并果子（Huffman 编码）：每次选最小的两个合并


3. 区间覆盖：按左端点排序，选择能覆盖最远的区间


4. 国王游戏：按 a*b 排序


5. 田忌赛马：双指针贪心

• 反证法：假设贪心不是最优，推出矛盾


• 归纳法


• 交换论证：从最优解出发，通过有限次交换变成贪心解


• 拟阵理论（Matroid）：贪心在拟阵上总是最优的

• 贪心 + 优先队列（如合并果子、任务调度）


• 贪心 + 线段树（如区间调度加强版）


• 贪心 + 并查集（如删数问题）

• 不是所有问题都能贪心


• 常见的假贪心例子：0-1 背包（不能贪心！）、非拟阵的集合选择


• 判断方法：尝试找反例，如果找不到，可以尝试证明

• 判断一个集合系统是否是拟阵


• 在拟阵上，贪心算法总是最优的


• Kruskal 求最小生成树本质上就是在图形拟阵上贪心

• 洛谷 P1223 排队接水（基础）


• 洛谷 P1090 合并果子


• 洛谷 P1080 国王游戏


• 洛谷 P2672 推销员（贪心 + 数据结构）