深高北-贪心算法
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
已预习

昨天 来自 广东
3悟了
2小时前 来自 北京
1我终于实名认证了!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
4小时前 来自 广东
1已预
6小时前 来自 浙江
1已预习
6小时前 来自 浙江
1已预习
7小时前 来自 浙江
1已预习
11小时前 来自 广东
1已预习
昨天 来自 广东
1那个异或和好像就是活动安排套个神秘东西
昨天 来自 广东
0
感谢教学
1小时前 来自 浙江
0已预习
2小时前 来自 浙江
0已预习
昨天 来自 广东
0已预习

昨天 来自 广东
0已预习
昨天 来自 广东
0已预习
昨天 来自 广东
0余知行已预习

昨天 来自 广东
0吴子墨预习
2天前 来自 广东
0张卓轩已预习
2天前 来自 广东
0邓睿宏已预习
2天前 来自 广东
0吴皓宁已预习
4天前 来自 广东
0李嘉树已预习
5天前 来自 广东
0





























































有帮助,赞一个