竞极 Ace

12 贪心算法

GESP C++ 五级：贪心算法系统梳理

核心目标：理解贪心算法的基本原理与适用条件，掌握“局部最优 → 全局最优”的推导逻辑，熟悉区间调度、背包问题、找零问题、任务调度等经典贪心模型，能判断贪心策略的正确性并给出反例。
贪心就是每一步都选当前看起来最好的，赌它能导出全局最优；关键在于证明“局部最优能推出全局最优”，否则需要用反例推翻并换用其他算法。

一、考纲定位

根据 CCF 官方考纲，五级知识点第（8）条明确要求：“掌握贪心算法的基本原理，理解最优子结构，能够使用贪心算法解决相关问题。 ”考核目标进一步要求：“熟悉二分法、分治法、贪心算法和递归算法的算法思想，能够根据实际情况选择合适的算法并完成解决相应的问题。”

贪心算法在五级考试中的考查分布：

考点 重要程度 典型考法
贪心算法核心思想 ★★★★★ 选择题（“贪心的核心思想是什么”）
贪心策略的正确性判断 选择题（判断某贪心策略能否得到最优解）
贪心反例辨析 选择题高频（如找零问题）
区间调度贪心 编程题、代码填空
背包问题（部分背包） ★★★★☆ 编程题
任务调度贪心
排序 + 贪心综合 ★★★★★ 编程题高频

二、贪心算法的核心思想

2.1 什么是贪心算法

贪心算法（Greedy Algorithm）在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法。

直观理解：就像选零食时每次都拿最贵的、排队接水时让接水最快的人先来——每一步都选“眼前最好的”。

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

贪心算法要正确，问题必须满足两个性质：

性质 含义 说明
贪心选择性质 每一步的局部最优选择能导致全局最优解 这是贪心算法正确性的关键
最优子结构 问题的最优解包含其子问题的最优解 与动态规划共享的性质

关键区分：贪心算法与动态规划的核心区别在于——贪心算法每一步做出不可撤销的选择，不保留备选方案；动态规划则保留所有可能的子问题解，通过状态转移求得全局最优。

2.3 贪心算法 vs 动态规划

对比项 贪心算法 动态规划
决策方式 每步做出不可撤销的局部最优选择 保留所有子问题解，统一决策
核心性质 贪心选择性质 + 最优子结构 最优子结构 + 重叠子问题
时间复杂度 通常 O(n log n)（排序为主） 通常 O(状态数 × 转移代价)
正确性 需要证明 状态转移方程保证
典型问题 区间调度、部分背包、找零（特定币值） 0/1 背包、最长公共子序列

三、贪心策略的正确性判断

3.1 贪心算法的“陷阱”

贪心算法最核心的风险是：局部最优不一定能推导出全局最优。一个经典的反例是找零问题：

假设硬币面值为 [5, 4, 1]，需要找零 8 元。

  • 贪心策略（每次选最大面值）：5 + 1 + 1 + 1 = 4 枚硬币
  • 最优解：4 + 4 = 2 枚硬币
    贪心策略失效！

因此，在使用贪心算法之前，必须先验证贪心策略是否能得到全局最优解。

3.2 判断贪心策略是否正确的三种方法

方法 思路 适用场景
反例法 尝试构造一个让贪心策略失效的输入 快速判断贪心是否错误
交换论证 证明任意最优解都可以通过交换变为贪心解，且不劣于原解 证明贪心正确
归纳法 证明每一步贪心选择后，剩余问题仍具有与原问题相同的结构

交换论证的核心思路：假设存在一个最优解，如果它和贪心解在某一步不同，通过交换操作可以将最优解调整为贪心解，且不破坏最优性，则贪心策略正确。在“巧夺大奖”题中，就是通过交换论证证明“放弃奖励最小的任务”不会使后续的解变差。

四、贪心算法的通用解题框架

4.1 四步框架

第一步：分析问题，确定贪心策略（每一步选什么）
第二步：验证贪心策略的正确性（反例/交换论证）
第三步：按贪心策略对数据进行排序或预处理
第四步：依次做出贪心选择，累加结果

4.2 贪心策略的常见方向

策略方向 典型问题 说明
按结束时间排序 区间调度 选结束最早的，留更多空间
按单位价值排序 部分背包 选性价比最高的
按耗时排序 排队接水 快的先来，减少总等待
按截止时间排序 任务调度 截止早的先做
按差值排序 平均分配 差最小的优先交换

五、经典贪心模型

5.1 区间调度（活动选择）

问题：给定 n 个活动的开始时间和结束时间，选择尽可能多的不重叠活动。

贪心策略：按结束时间从早到晚排序，每次选择结束最早且与已选活动不重叠的活动。

正确性：结束越早，留给后面活动的时间就越多，因此选择结束最早的活动不会比其他选择差。

struct Activity {
    int start, end;
};

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

int maxActivities(Activity a[], int n) {
    sort(a, a + n, cmp);
    int count = 1;
    int lastEnd = a[0].end;
    for (int i = 1; i < n; i++) {
        if (a[i].start >= lastEnd) {
            count++;
            lastEnd = a[i].end;
        }
    }
    return count;
}

5.2 排队接水

问题：n 个人排队接水，每人耗时不同，如何安排使所有人的平均等待时间最小？

贪心策略：按接水时间从短到长排序，快的先接。

正确性：用时短的人先接水，能让后面的人等待时间更短。假设两个人 A（1秒）、B（10秒），A先接的总等待为 0+1=1，B先接的总等待为 0+10=10。

sort(t, t + n);   // 按接水时间升序
long long total = 0, cur = 0;
for (int i = 0; i < n; i++) {
    cur += t[i];      // 当前人接完的时间
    total += cur;     // 累计所有人等待时间
}
// 平均等待时间 = total / n

5.3 部分背包（分数背包）

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

贪心策略：按单位价值（vᵢ/wᵢ）从高到低排序，优先装性价比最高的物品。

与 0/1 背包的区别：0/1 背包每个物品只能选或不选，不能分割，因此贪心策略失效，必须用动态规划。

struct Item {
    double weight, value, 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 totalValue = 0;
    for (int i = 0; i < n && W > 0; i++) {
        if (items[i].weight <= W) {
            totalValue += items[i].value;
            W -= items[i].weight;
        } else {
            totalValue += items[i].ratio * W;   // 装一部分
            W = 0;
        }
    }
    return totalValue;
}

5.4 任务调度（巧夺大奖）

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

贪心策略：按截止时间从早到晚排序，依次处理任务。用一个小根堆维护当前已选任务的奖励，当已选任务数量超过当前截止时间时，放弃奖励最小的任务。

priority_queue<int, vector<int>, greater<int>> pq;   // 小根堆
sort(a, a + n, [](Node x, Node y) {
    return x.t < y.t;   // 按截止时间升序
});

int sum = 0, tim = 0;
for (int i = 0; i < n; i++) {
    sum += a[i].r;
    pq.push(a[i].r);
    tim++;
    if (tim > a[i].t) {         // 任务数超过截止时间
        sum -= pq.top();        // 放弃奖励最小的
        pq.pop();
        tim--;
    }
}
cout << sum << endl;

5.5 平均分配

问题：给定两个数组 a 和 b，每个位置选择其中一个，使选择的元素个数在两边尽量相等，且总和最大。

贪心策略：先尽可能选大的，如果两边数量不相等，用差值最小的一对做交换。

for (int i = 0; i < 2 * n; i++) {
    ans += max(a[i], b[i]);
    if (a[i] > b[i]) {
        sum1++;
        q.push({a[i] - b[i], 1});   // 差值，标识
    } else {
        sum2++;
        q.push({b[i] - a[i], 2});
    }
}
// 数量不等时，从多的一边用最小差值换取平衡

六、GESP 五级贪心真题精讲

真题1：饮品调制（2026年9月）

题目：有 n 种原料，每种有存量 vᵢ 升、每升含糖 dᵢ 克。选择原料混合，使最终甜度恰好为 D，且总体积最大。

贪心思路：将原料按每升含糖量与目标甜度 D 的偏差分为“偏甜组”和“偏淡组”。偏甜组贡献正偏差，偏淡组贡献负偏差。为了让偏差抵消且体积最大，每升偏差越小的原料越优先使用。

struct Node { int v, d; };
bool cmp(const Node &a, const Node &b) {
    return a.d < b.d;   // 按每升含糖量升序（偏差从小到大）
}

关键点：贪心策略是“偏差越小的原料越优先用”，因为每升贡献的偏差越小，达到目标偏差所需的体积就越大。

真题2：平均分配（2025年3月）

题目：给定两个长度为 2n 的数组 a 和 b，每个位置选择其中一个，要求选出的 a 元素个数和 b 元素个数相等，求最大总和。

贪心思路：先每个位置都选较大的那个，统计 a 和 b 各被选了多少次。如果数量不等，就从多的一边选一个“差值最小”的位置，改选另一边。

关键点：用优先队列（小根堆）维护差值，每次取差值最小的进行交换，损失最小。

真题3：武器强化（2024年12月）

题目：小杨有 n 种武器，每种有初始熟练度 cᵢ。参加 m 场战斗，每场只能选一种武器使用，战斗后熟练度增加 aⱼ。要求最终第 1 种武器的熟练度严格大于其他所有武器，求最少需要额外花费多少金币来强化第 1 种武器。

贪心思路：枚举第 1 种武器需要达到的目标熟练度，然后贪心地用最少的金币强化其他武器（或强化第 1 种武器），使第 1 种武器严格大于其他武器。

关键点：涉及枚举 + 排序 + 贪心，是五级贪心题中难度较高的一类。

真题4：数字选取（2025年9月）

题目：从 1~n 中选取尽可能多的整数，使得任意两个不同的整数均互质。

贪心思路：数字 1 与任何数互质，必选。对于每个质数 p，它的所有倍数都不可选，因此每个质数最多只能选一个。答案 = 质数个数 + 1（加上 1）。

关键点：贪心 + 数论（埃氏筛统计质数个数），体现了五级“贪心与数论结合”的命题趋势。

真题5：贪心核心思想（选择题）

贪心算法的核心思想是（ ）。
A. 将问题分解为多个子问题，分别求解后合并
B. 在每一步选择中都采取当前状态下最优的选择
C. 通过保存所有可能的解，最终选择最优解
D. 随机选择，通过多次尝试找到最优解
答案：B

七、易错点汇总

  1. 不验证贪心策略就写代码：局部最优不一定全局最优，找零问题 [5,4,1] 找 8 元就是经典反例。
  2. 贪心策略与动态规划混淆：0/1 背包不能用贪心，部分背包才能用贪心。
  3. 排序关键字选错：区间调度按结束时间排（不是开始时间），排队接水按耗时排（不是编号排）。
  4. 忘记处理边界：区间调度中第一个活动必选，任务调度中小根堆为空时不能弹出。
  5. 贪心 + 优先队列遗漏：任务调度类问题需要用优先队列维护“当前最优”，不能只用普通排序。
  6. 比较函数写反：return a.end < b.end 是升序，写反会得到错误结果。
  7. 数据范围溢出：贪心累加求和时用 long long 防止溢出。
  8. 认为“贪心一定正确”：贪心算法需要证明或验证，不能想当然。
  9. 混淆部分背包和 0/1 背包：部分背包物品可分割，贪心有效；0/1 背包不可分割，贪心失效。
  10. 忽略“贪心 + 其他算法”的组合：五级常考“排序 + 贪心”“贪心 + 优先队列”“贪心 + 数论”等组合。

八、总结

贪心算法是 GESP 五级从“能写出正确程序”迈向“能设计最优策略”的关键一步。

  1. 贪心算法的核心是“每一步选当前最优”，但局部最优不一定推出全局最优。
  2. 贪心算法正确的前提是满足贪心选择性质和最优子结构。
  3. 使用贪心前必须验证策略：反例法快速判断，交换论证/归纳法证明正确。
  4. 区间调度按结束时间排序，任务调度按截止时间排序，排队接水按耗时排序。
  5. 部分背包按单位价值排序贪心，0/1 背包不能用贪心。
  6. 找零问题的反例 [5,4,1] 找 8 元是高频选择题考点。
  7. 任务调度类问题需要“排序 + 优先队列”组合，不能只用普通排序。
  8. 贪心常与数论、二分、优先队列结合，五级命题趋势是“贪心 + X”。
  9. 贪心累加求和时用 long long 防溢出。
  10. 多练“排队接水”“巧夺大奖”“平均分配”“饮品调制”四类真题，覆盖不同贪心模型。

复习建议：先理解贪心算法的核心思想和适用条件，重点掌握“反例法”和“交换论证”两种判断策略正确性的方法；再逐个攻克区间调度、排队接水、任务调度、部分背包四个经典模型，把标准代码写熟；然后练习“饮品调制”“平均分配”“武器强化”等真题，体会“贪心 + 排序/优先队列/数论”的组合考法；最后整理选择题中的高频反例，考前重点复习。