RootStack

C++ 算法技巧 — 贪心 (Greedy)

7分钟阅读

章节概述

贪心算法在每一步选择中都采取当前状态下最优的决策，从而希望最终结果也是最优的。

贪心与 DP 的核心区别：贪心每步只做一次选择且不回退；DP 考虑所有可能转移，选择全局最优。
贪心能用的情况通常需要满足贪心选择性质和最优子结构。

核心原理

1. 贪心选择性质

问题的最优解可以通过一系列局部最优选择得到。即：在第 k 步做出贪心选择后，剩余子问题的最优解与第 k 步选择组合，仍构成原问题最优解。

2. 贪心正确性证明方法

方法思路示例
交换论证法假设存在非贪心最优解，证明交换为贪心解后不会变差排队接水、活动安排
数学归纳法第 1 步贪心正确，假设前 k 步正确证第 k+1 步哈夫曼编码
反证法假设贪心不是最优，导出矛盾部分背包

3. 贪心常用模式

1. 按某种属性排序（性价比、结束时间、数值大小）
2. 顺序扫描，维护当前状态
3. 每一步贪心决策：
   - 排队接水: 按时间升序
   - 合并果子: 每次取最小两个 (用堆维护)
   - 部分背包: 按性价比降序
   - 活动安排: 按结束时间升序

关键数据结构

P1223 排队接水

题目: n 个人排队打水，每人需要 T[i] 时间。求一种排队顺序使得所有人的平均等待时间最小。

思路: 短作业优先——按打水时间升序排列，等待时间为前面所有人打水时间之和。

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
 
struct P { int t, id; };
bool cmp(P a, P b) { return a.t < b.t; }
 
int main() {
    int n;
    P p[1005];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> p[i].t;
        p[i].id = i + 1;
    }
    sort(p, p + n, cmp);
    double total = 0, cur = 0;
    for (int i = 0; i < n; i++) {
        cout << p[i].id << " ";
        total += cur;
        cur += p[i].t;
    }
    printf("\n%.2f\n", total / n);
    return 0;
}

P1090 [NOIP2004 提高组] 合并果子

题目: n 堆果子每堆重量 a_i，每次合并两堆消耗体力等于两堆重量之和，求合并成一堆的最小体力消耗。

思路: 每次合并最小的两堆（哈夫曼树思想），用优先队列（小根堆）维护。

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

P1106 删数问题

题目: 输入一个高精度正整数 n，去掉其中 s 个数字后剩下的数字按原顺序组成新数，求新数的最小值。

思路: 贪心策略: 每次从左到右找第一个比右边大的数字删除（这个数字的”贡献”太大），重复 s 次。

#include <iostream>
#include <string>
using namespace std;
 
int main() {
    string n;
    int s;
    cin >> n >> s;
    while (s--) {
        int i = 0;
        while (i < (int)n.size() - 1 && n[i] <= n[i + 1]) i++;
        n.erase(i, 1);
    }
    while (n.size() > 1 && n[0] == '0') n.erase(0, 1);
    cout << n << endl;
    return 0;
}

P2240 部分背包问题

题目: 体积为 M 的背包和 N 件物品，每件物品有体积 v_i 和价值 w_i，物品可任意切割（取体积的一部分则按比例获得价值）。求背包能装的最大总价值。

思路: 按性价比（价值/体积）降序排列，贪心装入，最后一件可能切割。

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
 
struct Item { double w, v, ratio; };
bool cmp(Item a, Item b) { return a.ratio > b.ratio; }
 
int main() {
    int n; double m;
    Item a[105];
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i].w >> a[i].v;
        a[i].ratio = a[i].v / a[i].w;
    }
    sort(a, a + n, cmp);
    double ans = 0;
    for (int i = 0; i < n && m > 1e-9; i++) {
        double take = min(m, a[i].w);
        ans += take * a[i].ratio;
        m -= take;
    }
    printf("%.2f\n", ans);
    return 0;
}

推荐练习题（洛谷）

相关技巧

  • 排序: 贪心通常需要排序预处理
  • 二分答案: 贪心算法常用于二分答案的 check 函数
  • 搜索: 贪心是搜索的剪枝/近似的替代方案
  • 前缀和: 区间贪心问题配合前缀和优化
  • C_堆_Heap: priority_queue 实现合并果子、哈夫曼编码
  • A_容器_Container: vector 排序后贪心遍历

多平台练习

| 洛谷 | 本题单 | 竞赛基础 |
| POJ (北大) | PKU JudgeOnline | 经典题目，适合巩固 |
| HDU (杭电) | HDU OJ | 暑期多校训练 |
| Codeforces | Codeforces | 国际竞赛，适合提升 |

关系图谱

反向链接