贪心算法最容易写出，也最容易写错。它通常只保留当前局面，然后做一个看起来最划算的选择；真正的难点不是代码，而是证明这个局部选择不会破坏全局最优解。

本文选择三道难度逐步上升的 Codeforces 题：先用排序决定拿硬币的顺序，再证明挑战巨龙的唯一安全次序，最后用“给未来留下空间”的原则决定树向哪边倒。

1. 判断一道题能否贪心

看到“最少、最多、任意顺序”时，可以先提出三个问题：

  1. 当前选择之后，未来需要保留哪些信息？
  2. 如果最优方案没有采用我的选择，能否交换成采用它而不变差？
  3. 做出选择后，剩余问题是否仍是同一类问题？

排序经常出现在贪心题里，但“排序后做”本身不是证明。需要解释排序改变了什么，以及为什么另一种次序不可能更优。

2. 160A · Twins：优先拿最大的硬币

查看官方题目

要从一组硬币中拿走尽可能少的枚数，使自己的金额严格大于剩余金额。设全部金额为 total，已拿金额为 chosen，目标就是：

1
chosen > total - chosen

为了用最少枚数达到阈值，每一次都应拿当前最大的硬币。把金额从大到小排序，累加到严格超过一半即可。

为什么最大的优先

假设某个最优方案拿了较小硬币 x，却没拿更大的硬币 y。把 x 换成 y 后，硬币枚数不变、总金额不会下降，因此仍然可行。不断交换，就能得到一个由若干枚最大硬币组成的最优方案。

这就是交换论证：不是声称“大的看起来更好”，而是说明任何最优解都可以被改造成我们的贪心解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> coins(n);
    int total = 0;
    for (int& coin : coins) {
        cin >> coin;
        total += coin;
    }

    sort(coins.rbegin(), coins.rend());

    int chosen = 0;
    for (int i = 0; i < n; ++i) {
        chosen += coins[i];
        if (chosen > total - chosen) {
            cout << i + 1 << '\n';
            break;
        }
    }
}
  • 时间复杂度：O(n log n)；
  • 空间复杂度：除排序存储外为 O(1)；
  • 易错点：题目要求严格更多，所以不能写成 >=。

3. 230A · Dragons：先挑战最弱的对手

查看官方题目

Kirito 只有在当前力量严格大于巨龙力量时才能获胜，胜利后得到非负奖励。将巨龙按力量从小到大排序并依次挑战。

为什么这个次序足够？假设当前连最弱的巨龙都打不过，那么更强的巨龙也打不过，已经不存在可行的第一步。反过来，只要能打败最弱者，力量就只会增加，不会让后面的选择变差。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
    int strength, n;
    cin >> strength >> n;

    vector<pair<int, int>> dragons(n);
    for (auto& [required, bonus] : dragons) {
        cin >> required >> bonus;
    }
    sort(dragons.begin(), dragons.end());

    for (const auto& [required, bonus] : dragons) {
        if (strength <= required) {
            cout << "NO\n";
            return 0;
        }
        strength += bonus;
    }

    cout << "YES\n";
}
  • 时间复杂度：O(n log n)；
  • 空间复杂度：O(n)；
  • 易错点：相等也无法获胜，判断条件是 strength <= required。

这里的证明依赖奖励非负。如果战胜某条巨龙会扣除力量，“先弱后强”就未必正确；检查假设是贪心证明的一部分。

4. 545C · Woodcutters：给右侧留下最大空间

查看官方题目

第 i 棵树位于 x[i]，高度为 h[i]。它可以保持站立、向左倒或向右倒，但不能碰到已经占用的位置或下一棵树。目标是砍倒尽可能多的树。

从左向右扫描，记 lastOccupied 为左侧方案占用到的最右位置。按以下优先级选择：

  1. 若 x[i] - h[i] > lastOccupied，向左倒；
  2. 否则，若它是最后一棵，或 x[i] + h[i] < x[i + 1]，向右倒；
  3. 否则保持站立，把 lastOccupied 更新为 x[i]。

为什么优先向左？向左倒后，右边界只是树根 x[i]；保持站立的右边界也相同，但少砍一棵。若不能向左，再尝试向右；只有右倒会撞到下一棵时才保留它。每一步都尽量缩小已处理前缀的最右占用位置，因此给未处理部分留下不少于其他选择的空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <limits>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> x(n), h(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> h[i];
    }

    long long lastOccupied = numeric_limits<long long>::lowest() / 4;
    int answer = 0;

    for (int i = 0; i < n; ++i) {
        if (x[i] - h[i] > lastOccupied) {
            ++answer;
            lastOccupied = x[i];
        } else if (i == n - 1 || x[i] + h[i] < x[i + 1]) {
            ++answer;
            lastOccupied = x[i] + h[i];
        } else {
            lastOccupied = x[i];
        }
    }

    cout << answer << '\n';
}
  • 时间复杂度：O(n)；
  • 空间复杂度：O(n)，也可边读边处理以进一步压缩；
  • 易错点：端点相碰也算冲突，所以比较必须使用严格不等号；坐标与高度相加减用 long long 更稳妥。

5. 三道题的贪心依据

题目 局部选择 保留的状态 正确性抓手
160A Twins 每次拿最大硬币 已拿金额 较小硬币可交换为较大硬币
230A Dragons 先打最弱巨龙 当前力量 最弱者不可战胜时无可行首步
545C Woodcutters 左倒优先，其次右倒 前缀最右占用点 让后缀可用空间不变小

6. 提交前的反例清单

  • “大于”是否误写成“大于等于”；
  • 排序方向是否与目标一致；
  • 相同关键字的先后是否影响答案；
  • 局部收益会不会让未来状态变差；
  • 第一项、最后一项和只有一个元素时是否成立；
  • 加减运算是否可能超过 int。

练习贪心时，建议为每道题写一句交换论证或“不领先”论证，再开始敲代码。下一步可以回到 算法练习路径 对照滑动窗口、前缀和与差分：它们同样压缩状态，但正确性依据并不相同。