5.10 贪心

贪心算法是指每次取得局部最优解，来达到全局最优解的方法。与动态规划方法类似的是，贪心算法能更大幅度地优化问题的时间复杂度；同样的，对于题目的条件要求也更高，往往要求选手能够有证明贪心算法正确性的把握。

形象地说，动态规划知道不需要搜索什么；而贪心知道需要搜索什么。

很多时候，「题目有贪心解法」是一件可遇不可求的事情，动态规划方法相对来说更加普适。不过，也有一些较为常见的贪心问题。

例题 1：力扣 452. 用最少数量的箭引爆气球

也就是「打气球」问题。

由于力扣使用 C++ 特性较多，提供 ACM 模式参考代码：

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
const int N = 1e5 + 4;
struct Seg {
    int l, r;
    void read() {
        cin >> l >> r;
    }
    bool operator< (const Seg& rhs) const {
        return r < rhs.r;
    }
};
Seg a[N];
int n;
int main() {
    cin >> n;
    for (int i=0; i<n; ++i) {
        a[i].read();
    }
    sort(a, a + n);
    int ans = 0;
    int ed = -1 << 30;
    for (int i=0; i<n; ++i) {
        if (a[i].l > ed) {
            ++ans;
            ed = a[i].r;
        }
    }
    cout << ans << endl;
    return 0;
}

例题 2：[NOIP2004]合并果子

做这道题可以回想一下哈夫曼树，哈夫曼编码。具体思路可以理解为先加入的就要一直搬着走，所以先加入最小的。

你需要一个能实时保持元素有序的集合，详见「堆」。

参考代码

#include <bits/stdc++.h>
using namespace std;
priority_queue<int, vector<int>, greater<int>> q;
int n;
int main() {
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        q.emplace(x);
    }
    int ans = 0;
    while (q.size() > 1) {
        int a = q.top(); q.pop();
        int b = q.top(); q.pop();
        ans += a + b;
        q.emplace(a + b);
    }
    cout << ans << endl;
    return 0;
}

贪心问题比较考验思维，所以，请保持思考。

推荐阅读：贪心