贪心

前置知识

排序

目标

贪心典型例题

What

贪心算法的核心就是一个字：贪。总是做出当前看来最优的选择。

因此可知，贪心算法不从整体去考虑，它做出的选择也是局部最优选择，从而达到全局优化选择。

我们只关注目前的利益，从而达到利益最大化，尽管贪心算法不一定能得到最优解，面对相当数量的一部分问题，我们是可以得到正确的答案的。

从问题的某一个初始解，一步步推论，保证每一步都是最为优化的，出发逐步逼近给定的目标，以尽可能快的地求得更好的解。

当接下来的任意一步都无法达到最优时，贪心算法结束。

贪心常见题型

1、按某种顺序排序后，然后逐个取(sort，多关键字排序，重载小于符号)

2、每次取集合中的最大/最小，更新答案（使用priority_queue）

1319：【例6.1】排队接水

// 题意：给出n个人每个人打水需要的时间，现在有一个水龙头，问这n个人完成打水，平均等待时间最小

#include <bits/stdc++.h>

using namespace std;

const int N = 5010;

struct node {
    int id;
    int time;
}a[N];

bool cmp1(node a, node b) {
    return a.time < b.time;
}

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i].time;
        a[i].id = i;
    }

    sort(a + 1, a + 1 + n, cmp1);

    double sum = 0;
    for (int i = 1; i <= n; i++) {
        if (n - i >= 1) sum += a[i].time * (n - i);
    }

    for (int i = 1; i <= n; i++) cout << a[i].id << ' ';
    puts("");
    printf("%.2lf\n", sum / n);

    return 0;
}

总结

贪心比较需要思维能力，最开始刚接触，没有什么解题经验的同学，我觉得可以不必从贪心入手。

先把其他算法都学了，贪心算法就知道一个理论，然后加上典型类型的例题，就可以去刷题了。

至于证明贪心，普及组不多加要求。

参考

【普及】贪心算法专项训练 - 题单 - 洛谷

维基百科-贪心