深高北-贪心算法
2026-06-05 17:38:48
发布于：广东
贪心算法笔记（C++版）
一句话理解
贪心算法：每一步都选当前看起来最优的选择，不管以后会怎样。
就像吃自助餐——每次只拿最贵的菜，最后不一定吃得最爽，但在某些问题上这就是最优解。
一、什么是贪心算法？
贪心算法：在每一步都做出当前状态下最好的选择，希望通过局部最优达到全局最优。
核心思想：只看眼前，不回头，不后悔。
特点：
- 步骤简单，容易想
- 不一定每次都对（需要证明贪心是正确的）
- 一旦正确，效率很高
二、贪心算法的基本框架
// 贪心的一般套路
1. 把问题分解成一步一步
2. 每步都选当前最好的
3. 做完所有步骤，得到答案
三、经典题目
题目1：活动安排（选最多的活动）
题目描述：有 n 个活动，每个活动有开始时间 s[i] 和结束时间 e[i]。同一个时间只能参加一个活动，问最多能参加几个活动。
贪心策略：按结束时间从小到大排序，每次选结束最早的、且不冲突的活动。
输入样例：
6
1 3
3 5
0 7
5 7
3 8
5 9
输出样例：
4
#include <iostream>
#include <algorithm>
using namespace std;
struct node {
int s, e;
};
bool cmp(node a, node b) {
return a.e < b.e; // 按结束时间排序
}
node a[1010];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i].s >> a[i].e;
}
sort(a, a + n, cmp);
int cnt = 1; // 至少能选一个
int lastEnd = a[0].e; // 当前最后一个活动的结束时间
for (int i = 1; i < n; i++) {
if (a[i].s >= lastEnd) { // 开始时间 >= 上次结束时间
cnt++;
lastEnd = a[i].e;
}
}
cout << cnt << endl;
return 0;
}
为什么按结束时间选是对的？：结束越早，留给后面的时间越多。
题目2：排队接水（平均等待时间最小）
题目描述：有 n 个人接水，第 i 个人接水需要 t[i] 分钟。问怎样排队能使所有人的平均等待时间最小？输出总等待时间。
贪心策略：按接水时间从小到大排队。
输入样例：
5
3 1 4 2 5
输出样例：
20
（等待时间 = 0 + 3 + (3+1) + (3+1+4) + (3+1+4+2) = 0+3+4+8+5=20）
#include <iostream>
#include <algorithm>
using namespace std;
int t[1010];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> t[i];
}
sort(t, t + n); // 从小到大排序
int sum = 0; // 总等待时间
int wait = 0; // 当前这个人要等多久
for (int i = 0; i < n; i++) {
sum += wait; // 加上这个人的等待时间
wait += t[i]; // 下一个人要多等当前这个人的时间
}
cout << sum << endl;
return 0;
}
为什么按接水时间排序是对的？：用时短的人先接水，后面的人等得更少。
题目3：找零钱（用最少硬币）
题目描述：有 1 元、5 元、10 元、20 元、50 元、100 元的硬币无限个。要支付 M 元，问最少需要多少硬币。
贪心策略：先用最大面额的硬币，不够再用小面额。
输入样例：
168
输出样例：
5
（100+50+10+5+2+1？不对，这是金额。注意：M=168时：100元1个+50元1个+10元1个+5元1个+1元3个？等等算错了。100+50=150，差18，10元1个=160，差8，5元1个=165，差3，1元3个=168。一共1+1+1+1+3=7个。）
#include <iostream>
using namespace std;
int coin[6] = {100, 50, 20, 10, 5, 1};
int main() {
int m;
cin >> m;
int cnt = 0;
for (int i = 0; i < 6; i++) {
int num = m / coin[i]; // 用多少个这种硬币
cnt += num;
m = m % coin[i]; // 剩下的钱
}
cout << cnt << endl;
return 0;
}
注意：这种贪心在人民币面额下是对的（因为每种面额都是更大面额的约数）。如果不是这种面额（比如1,3,4元，要付6元，贪心会选4+1+1=3个，但最优是3+3=2个），贪心不一定对。
四、贪心的正确性
贪心算法不一定总是对的！使用前需要判断：
| 情况 | 说明 |
|---|---|
| 适用 | 问题有“贪心选择性质”（局部最优能推出全局最优） |
| 不适用 | 当前选择会影响后面的选择 |
五、贪心 vs 其他算法
| 对比 | 贪心 | 动态规划 | 枚举 |
|---|---|---|---|
| 思路 | 每步选最优 | 考虑所有可能 | 全部试一遍 |
| 时间复杂度 | 通常 O(n log n) | O(n²) 或更高 | 可能很高 |
| 正确性 | 需要证明 | 一定正确 | 一定正确 |
| 适用场景 | 有贪心性质的问题 | 最优化问题 | 数据范围小 |
六、贪心常见题型
| 题型 | 贪心策略 |
|---|---|
| 活动安排 | 按结束时间排序 |
| 排队问题 | 按时间排序 |
| 区间选点 | 按右端点排序 |
| 删数问题 | 找第一个下降点删除 |
| 找零钱 | 用最大面额（特定面额下） |
七、总结
| 要点 | 内容 |
|---|---|
| 核心思想 | 每步都选当前最好的 |
| 优点 | 简单、高效 |
| 缺点 | 不一定正确 |
| 使用前 | 证明或确认贪心是正确的 |
| 经典应用 | 活动安排 |
记忆口诀
贪心每步选最好，局部最优不烦恼
活动安排按结束，排队接水按时长
用前必须想清楚，贪心性质要记牢
T3
#include <bits/stdc++.h>
using namespace std;
struct x
{
double n, u, a;
};
bool cmp(x a, x b)
{
return a.a > b.a;
}
void func()
{
int w, s;
x arr[100];
cin >> w >> s;
for(int i = 0; i < s; ++i)
{
cin >> arr[i].n >> arr[i].u;
arr[i].a = arr[i].u / arr[i].n;
}
sort(arr, arr + s, cmp);
double sum = 0.0;
for(int i = 0; i < s; ++i)
{
if(arr[i].n <= w)
{
w -= arr[i].n;
sum += arr[i].u;
}
else if(arr[i].n > w)
{
sum += (w * arr[i].a);
break;
}
if(w == 0)
break;
}
printf("%.2f", sum);
}
int main()
{
int k;
cin >> k;
for(int i = 0; i < k; ++i)
{
func();
cout << endl;
}
return 0;
}
全部评论 20
我终于实名认证了!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
4小时前 来自 广东
1
有帮助，赞一个