贪心有序
贪心有序
贪心算法（greedy algorithm），每一步行动总是按某种指标选取最优的操作。而且目光短浅，总是只看眼前，并不考虑以后可能造成的影响。
可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。
贪心问题，经常涉及：排序、堆等方法
策略
从最小/最大开始贪心，优先考虑最小/最大的数，从小到大/从大到小贪心。
在此基础上，衍生出了反悔贪心。
从最左/最右开始贪心，思考最前/最后的数的策略，把 n 个数的原问题转换成 n−1 个数（或更少）的子问题。
题型
排序类，按照一定顺序排序以后，从左往右依次选择
eg. 区间问题
堆类，每次从队顶选择
eg. 银行家算法、Dijstra、Huffman
序列
最小/最大
单序/双序配对
最左/最右
划分
枚举
交换论证法
相邻不同
反悔
在网络流中，寻找增广路的过程也是一种反悔贪心。
区间贪心
- 不相交
- 分组
- 选点
- 覆盖
- 合并
- 其他
字符串贪心
- 字典序最小/最大
- 回文串
数学贪心
- 基础
- 乘机
- 排序不等式
- 基本不等式
- 中位数
- 归纳法
- 其他
解释
适用范围
贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
贪心选择性质 Greedy-choice property
最优子结构 Optimal substructure
如果一个问题的最优解包含其子问题的最优解，那么称该问题具有最优子结构。
贪心算法通常采用一个非常直接的方法运用最优子结构，假定通过对原问题的贪心选择就可以得到子问题，我们只需要证明做出贪心选择后的子问题和贪心选择一起构成原问题的最优解。该方法隐式地运用了归纳法，证明了每一步贪心选择都能构成原问题的最优解。
证明
贪心算法有两种证明方法：反证法和归纳法。一般情况下，一道题只会用到其中的一种方法来证明。
- 反证法：如果交换方案中任意两个元素/相邻的两个元素后，答案不会变得更好，那么可以推定目前的解已经是最优解了。
- 归纳法：先算得出边界情况（例如
）的最优解 ，然后再证明：对于每个 ， 都可以由 推导出结果。
要点
常见题型
在提高组难度以下的题目中，最常见的贪心有两种。
- 「我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从小到大）选择。」。
- 「我们每次都取 XXX 中最大/小的东西，并更新 XXX。」（有时「XXX 中最大/小的东西」可以优化，比如用优先队列维护）
二者的区别在于一种是离线的，先处理后选择；一种是在线的，边处理边选择。
排序解法
用排序法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值。
后悔解法
思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。
交换论证法
交换论证法就是用知道头脑中的明了了的最优解时，在不改变最优解的前提下，能够将最优解调整为贪心解（现在有点生涩，一会有个例题以及对应解决方法可以结合着看）
区别
与动态规划的区别
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
常见问题类型：
活动选择问题
区间合并
霍夫曼编码
连接木棍的最低费用
部分背包
区间
按照起点排序的情况：
- 合并重叠区间： 如果问题的目标是合并重叠的区间，通常会选择按照区间的起点进行排序。这样可以确保相邻的区间在排序后是连续的，便于检测和合并重叠的区间。
- 区间调度问题： 如果问题是选择最多不重叠区间的问题（如最多安排的会议数目），按照起点排序有助于贪心算法的设计，每次选择结束时间最早的区间。
按照终点排序的情况：
最大不重叠区间数目： 如果问题的目标是选择最多不重叠的区间，通常会选择按照区间的终点进行排序。这样可以确保每次选择的区间结束时间较早，从而尽可能容纳更多的区间。
会议室问题
最小箭头问题： 如果问题是射爆气球的问题，可以选择按照区间的终点进行排序。这有助于用尽量少的箭头射爆所有气球。