2贪心

这是四段中第二个要学的东东

2.1引入

贪心算法（英语：$greedy$ $algorithm$），是用计算机来模拟一个「贪心」的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。

可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。

2.2解释

2.2.1适用范围

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

2.2.2证明

贪心算法有两种证明方法：反证法和归纳法。一般情况下，一道题只会用到其中的一种方法来证明。

反证法：如果交换方案中任意两个元素/相邻的两个元素后，答案不会变得更好，那么可以推定目前的解已经是最优解了。 归纳法：先算得出边界情况（例如 $n = 1$）的最优解 $F_1$，然后再证明：对于每个 $n，F_{n+1}$ 都可以由 $F_{n}$ 推导出结果。

2.3要点

2.3.1常见题型

在提高组难度以下的题目中，最常见的贪心有两种。

「我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从小到大）选择。」。 「我们每次都取 XXX 中最大/小的东西，并更新 XXX。」（有时「XXX 中最大/小的东西」可以优化，比如用优先队列维护） 二者的区别在于一种是离线的，先处理后选择；一种是在线的，边处理边选择。

2.3.2排序解法

用排序法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值。

2.3.3后悔解法

思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。

2.3.4区别

与动态规划的区别(这个后面会讲）
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

2.4例题：

#T1327. 动态求取最大值

注:这里需要用$STL$中的priority_queue,不然会超时,后面讲$STL$的

参考代码：

#include<bits/stdc++.h>
using namespace std;
priority_queue<int> q;
int main(){
	int n;
	cin >> n;
	while (n--) {
		int op;
		cin >> op;
		if(op == 1){
			int num;
			cin >> num;
			q.push(num);
		} else {
			cout << q.top() << endl;
			q.pop();
		}
	} 
	return 0;
}

#T1332. 动态求取最小值

其实这题和上一题一样只要输入num时输入-num，输出是输出-num就行了

还有这题，都是用priority_queue做的： P1090.合并苹果

剩下的题，都是贪心算法了
#P1650. 田忌赛马
#P1803. 凌乱的yyy / 线段覆盖
#T1333. 区间覆盖
#T1343. 数轴覆盖