贪心¶
前置知识¶
排序
目标¶
贪心典型例题
What¶
贪心算法的核心就是一个字：贪。总是做出当前看来最优的选择。
因此可知，贪心算法不从整体去考虑，它做出的选择也是局部最优选择，从而达到全局优化选择。
我们只关注目前的利益，从而达到利益最大化，尽管贪心算法不一定能得到最优解，面对相当数量的一部分问题，我们是可以得到正确的答案的。
从问题的某一个初始解，一步步推论，保证每一步都是最为优化的，出发逐步逼近给定的目标，以尽可能快的地求得更好的解。
当接下来的任意一步都无法达到最优时，贪心算法结束。
贪心常见题型¶
1、按某种顺序排序后，然后逐个取(sort，多关键字排序，重载小于符号)
2、每次取集合中的最大/最小，更新答案（使用priority_queue）
贪心在最优子结构的问题中尤为有效（最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解）。
贪心与dp的区别，贪心对每个子问题的解决方案都做出选择，不能回退。dp会保存以前的运算结果，并根据以前的结果进行选择，有回退功能。
有的时候，贪心并不是正确的，比如 01背包问题，贪心就会出错。贪心问题特别像逻辑题，方法很简单，但是证明却很难。考场上，不需要会证明。
贪心法证明的常见方法
- 反证法(假设、调整、做差)
- A>=B, A <= B, 证明A=B
- 数学归纳法
例题，【例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;
}
题单¶
一刷：
二刷：
总结¶
贪心比较需要思维能力，最开始刚接触，没有什么解题经验的同学，我觉得可以不必从贪心入手。
先把其他算法都学了，贪心算法就知道一个理论，然后加上典型类型的例题，就可以去刷题了。
至于证明贪心，普及组不多加要求。