竞极 Ace

4 贪心算法专项

GESP C++ 六级讲义：贪心算法专项

核心目标：在五级贪心基础上，深入掌握贪心算法的正确性证明方法，熟练运用区间调度、部分背包、任务调度等经典模型，能识别贪心失效的场景并给出反例，能解决GESP六级真题中的贪心综合问题。
贪心的本质是“每步选局部最优，赌它能导出全局最优”；六级的要求从“会用”升级为“会证、会辨、会组合”——能用交换论证证明策略正确，能用反例推翻错误策略，能在复杂场景中设计正确的贪心规则。

一、考纲定位

根据CCF官方考纲，六级知识内容中贪心算法与分治算法并列，要求“掌握贪心算法的基本原理，理解最优子结构，能够使用贪心算法解决相关问题”。

六级贪心与五级的核心区别：

维度 五级要求 六级要求
策略设计 套用经典模型 设计并验证新策略
正确性 知道策略正确即可 能用交换论证证明
反例辨析 了解找零反例 主动构造反例推翻错误策略
组合应用 贪心 + 排序 贪心 + 排序 + 优先队列 + 数论 + 树形结构
真题难度 普及− 普及/提高−

六级贪心真题覆盖了任务调度（ 游戏）、字符串划分、算法学习、路径覆盖等多种场景，命题趋势是“贪心 + X”的组合考查。

二、贪心算法的核心思想与正确性证明

2.1 贪心算法的两个核心性质

贪心算法正确的前提是问题同时满足两个性质：

性质 含义 验证方法
贪心选择性质 每步的局部最优选择能导致全局最优解 交换论证 / 归纳法
最优子结构 问题的最优解包含其子问题的最优解 与动态规划共享

2.2 交换论证法（证明贪心的核心工具）

交换论证的核心思想是：假设存在一个最优解，如果它和贪心解在某一步不同，通过交换操作可以将最优解调整为贪心解，且不破坏最优性。如果这个调整可以逐步进行，最终将最优解完全转化为贪心解，则贪心策略正确。

交换论证的通用步骤：

1. 假设 O 是一个最优解，G 是贪心解
2. 找到 O 中第一个与 G 不同的选择
3. 构造一个交换操作，将 O 调整为 O'，使得 O' 与 G 更接近
4. 证明交换后 O' 仍然是最优解（或至少不劣于 O）
5. 重复直到 O' = G，从而证明 G 也是最优解

注意事项：使用反证法假设 G ≠ O 时要小心，因为 G 和 O 可能选择不同但值相同。交换论证要确保每次交换“不使解变差”。

2.3 反例法（推翻贪心策略）

当怀疑贪心策略不正确时，主动构造反例是最快的方法。构造反例的思路：

  1. 让贪心选择“看起来最优”但实际“堵住了更好的路”。
  2. 让最优解通过“放弃局部最优”获得全局更优。

经典反例：0/1 背包。背包容量 10，物品 A（重6，价值10）、B（重5，价值8）、C（重5，价值8）。按单位价值贪心：A 的单位价值最高（10/6≈1.67），先选 A，剩余容量 4，无法再装任何物品，总价值 10。最优解是选 B+C，总价值 16。

经典反例：找零问题。硬币面值 [5, 4, 1]，找零 8 元。贪心选 5，剩余 3，再选 1+1+1，共 4 枚。最优解是 4+4，共 2 枚。

三、经典模型一：区间调度

3.1 问题描述

给定 n 个区间 [lᵢ, rᵢ]，选择尽可能多的不重叠区间。

3.2 贪心策略

按结束时间 rᵢ 升序排序，依次选择：如果当前区间的开始时间 ≥ 上一个已选区间的结束时间，则选择该区间。

3.3 正确性证明（交换论证）

证明思路：设贪心选择的第一个区间是 g（结束时间最早）。假设最优解 O 的第一个区间是 o。如果 g = o，无需交换。如果 g ≠ o，则 g 的结束时间 ≤ o 的结束时间。将 O 中的 o 替换为 g，由于 g 结束更早，剩余空间更大，不会减少后续可选区间的数量。因此交换后 O' 仍是最优解，且 O' 与贪心解在第一个选择上一致。对剩余区间重复此论证，最终证明贪心解就是最优解。

3.4 代码模板

struct Interval {
    int l, r;
};

bool cmp(const Interval &a, const Interval &b) {
    return a.r < b.r;   // 按结束时间升序
}

int maxNonOverlap(Interval a[], int n) {
    sort(a, a + n, cmp);
    int count = 1;
    int lastEnd = a[0].r;
    for (int i = 1; i < n; i++) {
        if (a[i].l >= lastEnd) {
            count++;
            lastEnd = a[i].r;
        }
    }
    return count;
}

真题对接（游戏，202403 六级） ：按结束时间排序任务，选择最早结束的任务，更新当前时间。这是区间调度模型在任务调度场景中的直接应用。

四、经典模型二：部分背包

4.1 问题描述

背包容量 W，n 个物品有重量 wᵢ 和价值 vᵢ，物品可以分割，求最大价值。

4.2 贪心策略

按单位价值 vᵢ/wᵢ 从高到低排序，优先装入性价比最高的物品。如果剩余容量不足以装下整个物品，就装入一部分。

4.3 正确性证明（交换论证）

证明思路：设贪心首先选择单位价值最高的物品 A。假设最优解 O 中没有使用 A（或使用 A 的比例小于贪心）。如果 O 中存在单位价值更低的物品 B，将 B 替换为等量的 A，总价值不会降低（因为 A 的单位价值 ≥ B）。因此存在一个最优解，其使用 A 的比例与贪心一致。对剩余容量重复此论证，最终贪心解是最优解。

4.4 代码模板

struct Item {
    double w, v, ratio;
};

bool cmp(const Item &a, const Item &b) {
    return a.ratio > b.ratio;   // 按单位价值降序
}

double fractionalKnapsack(Item items[], int n, double W) {
    sort(items, items + n, cmp);
    double total = 0;
    for (int i = 0; i < n && W > 0; i++) {
        if (items[i].w <= W) {
            total += items[i].v;
            W -= items[i].w;
        } else {
            total += items[i].ratio * W;
            W = 0;
        }
    }
    return total;
}

4.5 反例辨析：0/1 背包为什么不能用贪心

核心区别：部分背包物品可分割，0/1 背包物品不可分割。不可分割意味着“选择 A 就无法选择 B”，贪心的“不可撤销性”会导致局部最优堵死全局最优。反例：容量 10，A（重6，价值10）、B（重5，价值8）、C（重5，价值8）。贪心选 A 后无法再选，总价值 10；最优选 B+C，总价值 16。

五、经典模型三：任务调度（带截止时间）

5.1 问题描述

n 个任务，每个任务有截止时间 tᵢ 和奖励 rᵢ，每个单位时间只能做一个任务，求最大总奖励。

5.2 贪心策略

按截止时间升序排序，依次处理任务。用一个小根堆维护当前已选任务的奖励。如果已选任务数量超过当前截止时间，则放弃奖励最小的任务。

5.3 正确性证明（交换论证）

证明思路：按截止时间排序后，处理第 i 个任务时，如果已选任务数超过了 tᵢ，说明在 tᵢ 之前无法完成所有已选任务，必须放弃一些。放弃奖励最小的任务是最优的——因为放弃任何其他任务，损失都更大，而放弃最小任务不会减少可选任务的数量。对每个任务应用此论证，贪心解是最优解。

5.4 代码模板

struct Task {
    int deadline, reward;
};

bool cmp(const Task &a, const Task &b) {
    return a.deadline < b.deadline;
}

long long maxReward(Task a[], int n) {
    sort(a, a + n, cmp);
    priority_queue<int, vector<int>, greater<int>> pq;  // 小根堆
    long long sum = 0;
    int tim = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i].reward;
        pq.push(a[i].reward);
        tim++;
        if (tim > a[i].deadline) {
            sum -= pq.top();
            pq.pop();
            tim--;
        }
    }
    return sum;
}

真题对接（巧夺大奖） ：这就是任务调度模型的标准应用。

六、GESP 六级贪心真题精讲

真题1：算法学习（202409 六级）

题目描述：有 m 种算法，n 道题目。每道题包含若干算法，做一道题可掌握其所有算法。目标是用最少题目数让每种算法掌握度达到 k。

贪心思路：按每道题能增加的“掌握度”从大到小排序，依次选择题目，直到每种算法都达标。关键约束：如果某种算法的题目数量超过总题目数的一半，则无解。

struct Node { long long s, w; };  // s: 算法编号, w: 掌握度增量

bool cmp(const Node &a, const Node &b) {
    return a.w > b.w;   // 按掌握度增量降序
}

int main() {
    // 读入后按 w 降序排序
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        if (f[a[i].s] >= k) continue;   // 该算法已达标，跳过
        f[a[i].s] += a[i].w;            // 更新掌握度
        d[a[i].s]++;                     // 记录该算法学了几题
        sum++;
    }
    // 检查每种算法是否达标
    for (int i = 1; i <= m; i++) {
        if (d[i] > sum - d[i] + 1 || f[i] < k) {
            cout << -1;
            return 0;
        }
    }
    cout << sum;
}

核心考点：贪心 + 排序 + 可行性判定。策略是“优先选掌握度增量最大的题”，但需要额外检查解的存在性。

真题2：路径覆盖（202512 六级）

题目描述：一棵树，初始全白。可以将节点染黑，花费 c[i]。要求每个叶子到根的路径上至少有一个黑色节点，求最小花费。

贪心思路（树形贪心）：从叶子往上考虑。对每个节点 u，计算“将 u 染黑”和“不染黑 u，让子树各自解决”两种方案，取较小值。核心递推：

int getans(int u) {
    int ans = 0;
    for (auto v : children[u]) {
        ans += getans(v);
    }
    if (ans == 0) ans = INF;    // 叶子节点必须染黑
    ans = min(ans, c[u]);        // 比较“染黑u”和“子树各自解决”
    return ans;
}

核心考点：树形贪心（树形DP思想 + 贪心选择）。每个节点比较“自己解决”和“交给子树解决”的代价，取最小。

真题3：划分字符串（202509 六级）

题目描述：将字符串划分为若干子串，要求每个子串满足特定条件（如恰好包含某种字符），求最少划分段数。

贪心思路：贪心地尽量延长每个子串，当延长到无法满足条件时，才开启新的子串。这道题可以贪心解决，不需要动态规划。

核心考点：贪心 + 字符串处理。策略是“能延长就延长”，这是贪心在划分问题中的典型应用。

真题4：运送物资（202603 六级）

题目描述：涉及资源调度和贪心策略的综合题。

核心考点：贪心 + 构造。需要设计合理的排序规则和选择策略。

七、贪心算法的六级解题框架

7.1 通用四步框架（升级版）

第一步：分析问题，确定“每一步的选择对象是什么”
第二步：设计贪心策略（选什么、按什么顺序选）
第三步：验证策略正确性（交换论证 / 反例检测）
第四步：实现代码（排序 + 遍历 + 优先队列等数据结构）

7.2 六级贪心的策略设计模式

模式 核心思路 典型题
按结束时间选 结束越早，留给后面的空间越大 区间调度、游戏
按单位价值选 性价比越高越优先 部分背包
超限则弃最小 维持可行解，舍弃代价最小的 任务调度、算法学习
尽量延长 能延长就延长，无法延长才分割 划分字符串
树形自底向上 叶子往上，比较“自己解决”和“子树解决” 路径覆盖
前缀和思想 维护当前最优状态，逐步扩展 运送物资、选数

八、易错点汇总

  1. 不验证策略就写代码：六级贪心题陷阱更多，必须先做反例检测。
  2. 贪心与动态规划混淆：0/1 背包、选数类问题需要用 DP，不是贪心。
  3. 排序关键字选错：区间调度按结束时间（不是开始时间），任务调度按截止时间。
  4. 忘记处理不可行情况：如“算法学习”中需要检查解是否存在，不存在输出 -1。
  5. 优先队列方向错误：任务调度需要“放弃奖励最小的”，用小根堆；如果需要“优先选最大的”，用大根堆。
  6. 树形贪心遗漏边界：叶子节点必须特殊处理（ans == 0 → ans = INF），否则会返回 0 导致错误。
  7. 贪心策略的“局部”范围理解错误：六级题中“局部”可能是一个子树、一个前缀、一个窗口，不一定是单个元素。
  8. 整数溢出：奖励累加用 long long。
  9. 认为“所有贪心都正确”：六级真题中明确有反例辨析题，需要能判断策略是否成立。
  10. 忽略“贪心 + 其他算法”的组合：六级常考“贪心 + 排序 + 优先队列 + 树形结构”。

九、速查表

模型 贪心策略 数据结构 正确性关键
区间调度 按结束时间升序，选不重叠的 排序 结束越早，剩余空间越大
部分背包 按单位价值降序，优先装 单位价值越高越优先
任务调度 按截止时间升序，超时弃最小 排序 + 小根堆 放弃代价最小的不劣于其他选择
划分字符串 尽量延长每个子串 双指针 延长不劣于提前分割
树形贪心 叶子往上，比较“自己解决/子树解决” DFS + 贪心 每个节点的最优子结构独立
0/1 背包 ❌ 贪心失效 — 反例：容量10，A(6,10), B(5,8), C(5,8)
找零问题 ❌ 特定面值下失效 反例：[5,4,1] 找 8 元

十、总结

贪心算法在GESP六级中从“会用”升级为“会证、会辨、会组合”。

  1. 贪心的核心是“每步选局部最优”，但六级要求你能证明它确实能导出全局最优。
  2. 交换论证是证明贪心正确性的核心工具：将最优解逐步调整为贪心解，且不使解变差。
  3. 反例法是推翻错误贪心策略最快的方法：构造一个让贪心“堵死”最优路的场景。
  4. 区间调度按结束时间排序，任务调度按截止时间排序，部分背包按单位价值排序。
  5. 任务调度类问题需要“排序 + 小根堆”，超限时放弃代价最小的任务。
  6. 树形贪心从叶子往上递推，比较“自己解决”和“子树解决”的代价。
  7. 0/1 背包和部分背包的核心区别是“物品是否可分割”，前者不能用贪心。
  8. 六级贪心的命题趋势是“贪心 + X”：贪心 + 排序 + 优先队列 + 树形结构 + 字符串处理。
  9. 写完贪心代码前，先做反例检测：如果找不到反例，再尝试交换论证。
  10. 多练“算法学习”“路径覆盖”“划分字符串”“游戏”四道真题，覆盖排序贪心、树形贪心、字符串贪心和区间调度四种模型。

复习建议：先复习五级的经典模型（区间调度、部分背包、任务调度），确保模板代码闭卷能写；然后重点攻克“交换论证”和“反例构造”两项六级新增能力，手动模拟证明过程；接着练习“算法学习”和“路径覆盖”两道真题，体会“贪心 + 可行性判定”和“树形贪心”的解题思路；最后整理0/1背包和找零问题的反例，考前重点记忆。考试中先判断题目是否满足贪心条件，再设计策略并用反例快速验证，最后实现代码并检查边界。