深高北-贪心算法

张kk

2026-05-30 20:20:20

发布于：广东

2阅读

0回复

0点赞

贪心算法笔记（C++版）

一句话理解

贪心算法：每一步都选当前看起来最优的选择，不管以后会怎样。

就像吃自助餐——每次只拿最贵的菜，最后不一定吃得最爽，但在某些问题上这就是最优解。

一、什么是贪心算法？

贪心算法：在每一步都做出当前状态下最好的选择，希望通过局部最优达到全局最优。

核心思想：只看眼前，不回头，不后悔。

特点：

步骤简单，容易想
不一定每次都对（需要证明贪心是正确的）
一旦正确，效率很高

二、贪心算法的基本框架

// 贪心的一般套路
1. 把问题分解成一步一步
2. 每步都选当前最好的
3. 做完所有步骤，得到答案

三、经典题目

题目1：活动安排（选最多的活动）

题目描述：有 n 个活动，每个活动有开始时间 s[i] 和结束时间 e[i]。同一个时间只能参加一个活动，问最多能参加几个活动。

贪心策略：按结束时间从小到大排序，每次选结束最早的、且不冲突的活动。

输入样例：

输出样例：

#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

输出样例：

（等待时间 = 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 元，问最少需要多少硬币。

贪心策略：先用最大面额的硬币，不够再用小面额。

输入样例：

输出样例：

（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²) 或更高	可能很高
正确性	需要证明	一定正确	一定正确
适用场景	有贪心性质的问题	最优化问题	数据范围小

六、贪心常见题型

题型	贪心策略
活动安排	按结束时间排序
排队问题	按时间排序
区间选点	按右端点排序
删数问题	找第一个下降点删除
找零钱	用最大面额（特定面额下）