算法笔记:AcWing - 贪心算法

算法笔记:AcWing - 贪心算法

Ginkgo True love prevails.

💡 写在前面:贪心不是一种算法,而是一种思维方式。它的核心就一句话:每一步都做出当前看起来最优的选择。但难点在于——你怎么证明这个”局部最优”能推出”全局最优”?这篇笔记会带你理解贪心的本质。


什么是贪心?

核心思想:每一步都选择当前状态下看起来最优的决策,期望通过一系列局部最优达到全局最优。

形象理解:想象你在爬山,贪心就是”每次都往最陡的方向走”。但问题是——你可能爬到的是个小山丘,而不是真正的最高峰。

关键特点:

  • ✅ 没有固定模板:贪心是思路,不是套路
  • ✅ 短视行为:只看眼前,不管长远
  • ✅ 难点在证明:为什么这样贪心是对的?

什么时候能用贪心?
只有当问题具有贪心选择性质和最优子结构时,贪心才能得到最优解。简单说就是:

  1. 局部最优能推出全局最优
  2. 问题的最优解包含子问题的最优解

⚠️ 重要提醒:如果问题不是”单峰”的(有多个局部最优),贪心很可能掉进陷阱!


区间问题

区间问题是贪心的经典应用场景。核心思路:先排序,再扫描。


🎯 区间选点

问题描述:给定 N 个闭区间 [ai, bi],在数轴上选择尽量少的点,使得每个区间内至少包含一个点。输出最少点数。

贪心策略:

  1. 将所有区间按右端点从小到大排序
  2. 依次枚举每个区间:
    • 如果当前区间未被覆盖 → 选择它的右端点
    • 如果已被覆盖 → 跳过

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main() {
int n = next<int>();
vector<pii> arr(n);
for (int i = 0; i < n; i++)
arr[i] = {next<int>(), next<int>()};

// 按右端点排序
sort(arr.begin(), arr.end(), [](pii u, pii v) {
return u.second < v.second;
});

int cnt = 0, last = -INF; // last 记录上一个选的点
for (int i = 0; i < n; i++) {
auto [l, r] = arr[i];
if (l <= last) continue; // 已被覆盖
else {
cnt++;
last = r; // 选右端点
}
}
cout << cnt;
}

🤔 灵魂三问

Q1:为什么要按右端点排序,而不是左端点?

答:想象你在”消灭”区间。右端点越小的区间,它的”生存空间”越靠左,能覆盖它的点的选择范围越窄。这种区间最”挑剔”,必须优先满足!

1
2
区间 A: [1, 2]   ← 右端点小,只能选 1 或 2
区间 B: [1, 10] ← 右端点大,1~10 都能选

如果先处理 B,选了 10,那 A 就没人管了。但如果先处理 A,选了 2,B 也被覆盖了。先满足挑剔的,宽松的后面自然能沾光。


Q2:为什么选右端点,不选左端点或中间?

答:选右端点是为了让这个点尽可能覆盖后面的区间。

1
2
3
区间 A: [1, 5]
区间 B: [4, 8]
区间 C: [7, 10]
  • 如果选 A 的左端点 1:只能覆盖 A
  • 如果选 A 的右端点 5:能覆盖 A 和 B!

右端点是当前区间能贡献的”最远覆盖点”,当然选它!


Q3:怎么证明这个贪心是对的?

答:用反证法 + 构造法。

设我们的贪心策略选了 cnt 个点,对应 cnt 个互不相交的区间(因为每个新区间都没被前一个点覆盖)。

关键观察:这 cnt 个区间两两不相交,所以至少需要 cnt 个点(每个区间至少一个点,且不能共用)。

既然任何方案都至少需要 cnt 个点,而我们的贪心正好用了 cnt 个点,那贪心就是最优的!∎


🔗 最大不相交区间数量

问题描述:给定 N 个区间,选出尽量多的区间,使得它们两两不相交。求最多能选多少个。

答案:和区间选点做法完全一致!

为什么? 这两题是对偶问题:

  • 区间选点:最少用多少个点,覆盖所有区间
  • 最大不相交区间:最多选多少个区间,使得它们不共用任何点

根据上面的证明,贪心选出的 cnt 个区间是互不相交的,且任何方案都不可能超过 cnt 个。所以答案就是 cnt。

💡 数学之美:这两个问题本质是同一个问题的两面,就像”最少需要多少个哨兵看守所有城堡”和”最多能建多少个互不瞭望的城堡”。


📦 区间分组

问题描述:给定 N 个区间,将它们分成若干组,使得每组内部的区间两两不相交,求最小组数。

贪心策略:

  1. 按左端点从小到大排序
  2. 依次处理每个区间,判断能否放入某个现有组
  3. 如果能放 → 放入并更新该组的右端点;否则 → 开新组

核心问题:如何快速判断”能否放入某个组”?

一个区间能放入某组的条件:它的左端点 > 该组所有区间的最大右端点。

所以需要维护:所有组的最大右端点,并快速找到 < 当前左端点 的那个。


解法一:multiset

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main() {
int n = next<int>();
vector<pii> arr(n);
for (int i = 0; i < n; i++)
arr[i] = {next<int>(), next<int>()};

sort(arr.begin(), arr.end()); // 按左端点排序

multiset<int> st; // 存储每组的最大右端点
for (auto [l, r] : arr) {
auto it = st.lower_bound(l); // 找 >= l 的最小值
if (it == st.begin()) {
// 所有组的右端点都 >= l,无法放入,开新组
st.insert(r);
} else {
// 存在右端点 < l 的组,放入并更新
--it;
st.erase(it);
st.insert(r);
}
}
cout << st.size();
}

解法二:小根堆(更优)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main() {
int n = next<int>();
vector<pii> arr(n);
for (int i = 0; i < n; i++)
arr[i] = {next<int>(), next<int>()};

sort(arr.begin(), arr.end());

// 小根堆维护每组的最大右端点
priority_queue<int, vector<int>, greater<int>> heap;

for (auto [l, r] : arr) {
if (heap.empty() || heap.top() >= l) {
// 无法放入任何组,开新组
heap.push(r);
} else {
// 放入右端点最小的那个组,并更新
heap.pop();
heap.push(r);
}
}
cout << heap.size();
}

为什么堆更优?

  • multiset:O(n log n),但常数较大
  • priority_queue:O(n log n),常数小,代码更简洁

💡 理解技巧:把每个组想象成一个”教室”,右端点是这个教室当前课程的结束时间。新课程来了,看有没有教室已经空出来了(结束时间 < 新课程开始时间),有就用,没有就开新教室。


🛤️ 区间覆盖

问题描述:给定 N 个区间和一个目标区间 [st, ed],选出最少的区间,使得它们的并集能覆盖 [st, ed]。

贪心策略:

  1. 按左端点从小到大排序
  2. 从 st 开始,在所有能覆盖当前起点的区间中,选右端点最大的
  3. 更新起点为这个最大右端点,重复直到覆盖 ed

直观理解:想象你在铺路,每次都要选能接上当前路面、且能铺得最远的那块砖。

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
32
33
34
int main() {
int st = next<int>(), ed = next<int>(), n = next<int>();
vector<pii> arr(n);
for (int i = 0; i < n; i++)
arr[i] = {next<int>(), next<int>()};

sort(arr.begin(), arr.end());

int res = 0;
bool ok = false;

for (int i = 0; i < n; i++) {
int j = i, r = -INF;
// 在所有左端点 <= st 的区间中,找右端点最大的
while (j < n && arr[j].first <= st) {
r = max(r, arr[j].second);
j++;
}

if (r < st) break; // 无法覆盖,失败

res++;
if (r >= ed) {
ok = true;
break;
}

st = r; // 更新起点
i = j - 1; // 回退一位(循环会 i++)
}

if (!ok) res = -1;
cout << res;
}

时间复杂度:O(n log n)(排序)+ O(n)(扫描)= O(n log n)


Huffman 树

问题描述:给定 n 个权值,构造一棵二叉树,使得带权路径长度最小。每次合并两个节点,合并代价是两节点权值之和。

贪心策略:每次合并权值最小的两个节点。

为什么对?

  1. 权值最小的两个节点,深度一定最深(否则可以交换使答案更优)
  2. 它们可以互为兄弟(不影响最优性)

实现:用小根堆维护

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main() {
int n = next<int>();
priority_queue<int, vector<int>, greater<int>> q;

for (int i = 0; i < n; i++)
q.push(next<int>());

int ans = 0;
while (q.size() > 1) {
int u = q.top(); q.pop();
int v = q.top(); q.pop();
q.push(u + v);
ans += u + v; // 累加合并代价
}
cout << ans;
}

应用场景:

  • 数据压缩(Huffman 编码)
  • 最优合并策略

时间复杂度:O(n log n)


排序不等式

排序不等式:设有两组数 a₁ ≤ a₂ ≤ ... ≤ aₙ 和 b₁ ≤ b₂ ≤ ... ≤ bₙ,则:

简单说:同序和 ≥ 乱序和 ≥ 逆序和


💧 打水问题

问题描述:n 个人排队打水,第 i 个人需要 t[i] 时间。求总等待时间最小的排队顺序。

贪心策略:按打水时间从小到大排序。

直观理解:让打水快的人先打,后面的人等待时间就短。如果让慢的人先打,所有人都要等他很久。

数学推导:
设排序后的时间为 t₁ ≤ t₂ ≤ ... ≤ tₙ,则:

  • 第 1 个人等待 0
  • 第 2 个人等待 t₁
  • 第 3 个人等待 t₁ + t₂
  • …
  • 第 i 个人等待 t₁ + t₂ + ... + tᵢ₋₁

总等待时间:

系数 (n-i) 是递减的,根据排序不等式,t 应该递增排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main() {
int n = next<int>();
vector<int> t(n);
for (int i = 0; i < n; i++)
t[i] = next<int>();

sort(t.begin(), t.end());

i64 ans = 0;
for (int i = 0; i < n; i++)
ans += t[i] * (n - i - 1);

cout << ans;
}

绝对值不等式

🏪 货仓选址

问题描述:在数轴上有 n 个商店,位置分别为 x₁, x₂, ..., xₙ。要建一个货仓,使得所有商店到货仓的距离之和最小。求货仓的最佳位置。

贪心策略:货仓建在中位数位置。

为什么? 用配对法理解:

把商店按位置排序后,考虑最左和最右的商店 x₁ 和 xₙ:

  • 无论货仓建在哪,|x - x₁| + |x - xₙ| 的最小值就是 xₙ - x₁(当 x 在两者之间时取到)

同理,x₂ 和 xₙ₋₁ 配对,x₃ 和 xₙ₋₂ 配对…

结论:

  • n 为奇数:货仓建在正中间的商店 x[n/2]
  • n 为偶数:货仓建在中间两个商店之间的任意位置(通常取 x[n/2])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main() {
int n = next<int>();
vector<int> x(n);
for (int i = 0; i < n; i++)
x[i] = next<int>();

sort(x.begin(), x.end());

i64 ans = 0;
for (int i = 0; i < n; i++)
ans += abs(x[i] - x[n / 2]); // 中位数

cout << ans;
}

💡 形象理解:想象你在拉橡皮筋,左边商店把你往左拉,右边商店把你往右拉。平衡点就是中位数!


推公式型贪心

很多贪心问题需要先模拟、找规律、推公式。核心方法:分析交换两个元素的影响。


🐂 耍杂技的牛

问题描述:n 头牛叠罗汉,第 i 头牛有体重 w[i] 和力量 s[i]。每头牛的危险系数 = 它上面所有牛的体重之和 - 它的力量。求最大危险系数的最小值。

贪心策略:按 w[i] + s[i] 从小到大排序。


🤔 为什么是 w + s?(详细证明)

考虑相邻的两头牛 i 和 i+1,分析交换它们的影响。

关键观察:交换相邻两头牛,不影响其他牛的危险系数,只影响这两头牛。

设前 i-1 头牛的体重和为 W,则:

交换前(i 在上,i+1 在下):

  • 牛 i 的危险系数:W - s[i]
  • 牛 i+1 的危险系数:W + w[i] - s[i+1]
  • 最大危险系数:max(W - s[i], W + w[i] - s[i+1])

交换后(i+1 在上,i 在下):

  • 牛 i+1 的危险系数:W - s[i+1]
  • 牛 i 的危险系数:W + w[i+1] - s[i]
  • 最大危险系数:max(W - s[i+1], W + w[i+1] - s[i])

去掉公共项 W,比较:

  • 交换前:max(-s[i], w[i] - s[i+1])
  • 交换后:max(-s[i+1], w[i+1] - s[i])

两边同时加上 s[i] + s[i+1](不改变大小关系):

  • 交换前:max(s[i+1], w[i] + s[i])
  • 交换后:max(s[i], w[i+1] + s[i+1])

结论:如果 w[i] + s[i] < w[i+1] + s[i+1],则交换前的最大值更小,不应该交换。

所以最优排列是:按 w + s 递增排序!∎


代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main() {
int n = next<int>();
vector<pii> cows(n); // {w, s}
for (int i = 0; i < n; i++) {
int w = next<int>(), s = next<int>();
cows[i] = {w, s};
}

// 按 w + s 从大到小排序(代码里是倒着遍历)
sort(cows.begin(), cows.end(), [](pii a, pii b) {
return a.first + a.second > b.first + b.second;
});

i64 ans = -INF, sum = 0;
for (int i = n - 1; i >= 0; i--) { // 从 w+s 最小的开始
auto [w, s] = cows[i];
ans = max(ans, sum - s); // 当前牛的危险系数
sum += w; // 累加体重
}

cout << ans;
}

💡 理解技巧:w + s 可以理解为”综合负担能力”。w + s 小的牛,要么体重轻(压别人少),要么力量小(容易被压),应该放上面。


📝 贪心总结

问题类型 贪心策略 排序方式 核心思想
区间选点 选右端点 右端点升序 先满足挑剔的
最大不相交区间 同上 右端点升序 对偶问题
区间分组 放入最早结束的组 左端点升序 小根堆维护
区间覆盖 选能接上且最远的 左端点升序 每次铺最远
Huffman 树 合并最小的两个 小根堆 深度最深
打水问题 快的先打 时间升序 排序不等式
货仓选址 建在中位数 位置升序 配对法
耍杂技的牛 按 w+s 排序 w+s 升序 交换分析法

🎯 贪心解题套路

  1. 猜贪心:根据直觉猜一个贪心策略
  2. 验证:
    • 举反例:能不能找到反例?
    • 交换分析:交换两个元素会变好吗?
    • 数学归纳:能证明吗?
  3. 实现:通常是”排序 + 扫描”

🍂 最后的话:贪心的难,不在于代码,而在于证明。多做题、多思考”为什么这样是对的”,你会逐渐培养对贪心的直觉。记住:能证明的贪心才是好贪心!

  • Title: 算法笔记:AcWing - 贪心算法
  • Author: Ginkgo
  • Created at : 2026-04-12 16:12:02
  • Updated at : 2026-04-12 16:21:49
  • Link: https://g1nkgo7.github.io/2026/04/12/算法笔记-AcWing-贪心/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments