贪心
贪心是一种思想，而不是一种具体的算法，没有固定的写法。
下面介绍几种贪心经典算法来引入贪心的思想。
贪心的熟练运用需要通过大量的做题自行提高。
贪心在算法竞赛中具有极广的应用，可以说 $50%$ 的题目都用到了贪心的思想。
区间选点：
给定 $n$ 个区间 $[l_i,r_i]$，选择最少的点，使得每个区间内至少包含一个选出的点。（只关心数量）
将区间按 $l_i$ 为第一关键字升序，$r_i$ 为第二关键字降序排序。
考虑排序后的 $n$ 个区间，从第一个区间开始，用一个点覆盖尽可能多的区间，即：$l_i\leq r_1$ 的区间。从第一个满足 $l_i>r_1$ 的区间开始，同样考虑。（实际上选的点就是 $r_1$）
证明 $1$：
设最优解为 $ans$，上述解法求出为 $res$。
易得：$ans\leq res$。
对于 $res$ 个点，每一个点都需要用至少一个区间去覆盖，同时任意两个区间之间不会相交。因为如果相交，那么在上述算法过程中会被算在前一个区间上，不符合算法过程。即：$ans\geq res$。
综上：$ans=res$。
证明 2：
对于 $n$ 个区间，初始没有任何区间被覆盖，但最终所有点都会被覆盖。因此不妨选择第一个区间 $[l_1,r_1]$ 作为第一个被选的区间，考虑哪些区间是通过在 $[l_1,r_1]$ 中选择一个点就能被覆盖的：和 $[l_1,r_1]$ 有交集的区间：
- $l_i<l_1,r_i\in [l_1,r_1]$
- $[l_i,r_i]\subset [l_1,r_1]$ 覆盖 $[l_i,r_i]$ 一定会覆盖 $[l_1,r_1]$，所以可以去掉 $[l_1,r_1]$。
- $r_i>r_1,l_i\in[l_1,r_1]$
第一类和第三类不能仅仅通过一个点覆盖，需要两个点，而区间 $[l_1,r_1]$ 被划为那一个点，是无法确定的。
同时，覆盖点的数量只和区间有关，而和顺序无关。所以，将区间排序，有序后，由于 $[l_1,r_1]$ 是最靠左的，所以 $[l_1,r_1]$ 不会面对第一类还是第三类的抉择，一定是第三类。往后一样考虑即可。
最多不相交区间：
给定 $n$ 个区间 $[l_i,r_i]$，选择最多的区间，使得任意区间之间不相交。（只关心数量）
将区间按 $r_i$ 升序。
考虑排序后的 $n$ 个区间，从第一个区间开始，尽可能多地选择区间。$l_i>r_1$ 的区间。因为 $r_i\geq r_1,l_i\leq r_1$ 的区间和 $[l_1,r_1]$ 相交。
证明 1：
设最优解为 $ans$，上述解法求出为 $res$。
易得：$ans\geq res$。
对于已经求出来的 $res$ 个区间，若存在第 $res+1$ 个区间满足不与其它任意区间相交，设这个区间为 $[L,R]$，则一定满足 $\exist\ r_i<L\land R<l_{i+1}$。而如果存在这样的区间 $[L,R]$ 在上述算法中一定是会被考虑到的，所以不存在这样的区间，即：$ans<=res$。
综上：$ans=res$。
证明 2：
考虑选完的最终 $m$ 个区间，满足：$l$ 和 $r$ 分别严格单增。
同样地，考虑第一个区间，第一个区间的 $r$ 一定是最小的。若不是最小的，则换成 $r$ 最小的，并不会使答案变劣。后面的也同理，不会让答案变劣。因此将区间按 r 升序，这样得到的区间满足每次能取到的 $r$ 一定是最小的，只要考虑 $l$ 即可。
addition：
其实可以发现：“区间选最少点”和“最多不相交区间”本质是相同的。（即：同一份代码即可以解决前者也可以解决后者）
因为区间选点中的点所覆盖的区间都是相交的，选择了其中之一就不能再选择其它区间。所以“一个点对应了一个区间”。选出的区间对应于选出的点。
区间分组：
给定 $n$ 个区间 $[l_i,r_i]$，把区间分成最少的组，使得每组内的任意区间之间不相交。（只关心数量）
结合前文，在区间选点中，一个点对应的区间不能在一个组内。所以一个点对应的每个区间都对应了一个组。考虑这若干个组，在下一个点的若干个区间中，$l$ 最小的那个可以放进这若干个组中的任何一个，而放进 $r$ 最小的那个组最优。因为小的 $l$ 能放的组，大的也能放；而小的 $l$ 不能放的组当然也放不了。即：反之不优。若不能放到之前已有的组中，则新开一个组。
所以从前往后考虑每一个点，用优先队列维护每一个点对应的区间的 $r$ 的有序性。
最后的一个组对应一个优先队列。
区间覆盖：
给定 $n$ 个区间 $[l_i,r_i]$，选择最少的区间覆盖 $[s,t]$。（只关心数量）
考虑第一个，覆盖 $[s,h]$（前缀）的一个区间。一定是满足 $l\leq s$ 的 $r$ 最大的一个区间。那么后续对 $(h,t]$ 同样处理就好了。
所以对 $n$ 个区间按 $l_i$ 为第一关键字升序，$r_i$ 为第二关键字升序排序。每次找到 $l_i\leq s$ 的最大 $r_i$ 即可。
合并果子：
Huffman 树。
给定 $n$ 堆果子，每次可以花费两堆果子数目之和的代价合并两堆（会形成新的一堆）。求合并成 $1$ 堆的最小代价。
假设仅考虑选择两堆合并，那一定是果子数目最少的两堆。所以从直觉上讲，每次选择数量最少的两堆合并即可。
但是正向考虑每次操作不易理解，可以从“贡献”角度入手。考虑每一堆果子（初始的 $n$ 堆）被会被算几次。
考虑将果子合并的过程抽象成一棵二叉树：若合并 $x$ 号堆和 $y$ 号堆果子并形成一个 $z$ 号堆果子，则将 $z$ 号结点的左儿子设为 $x$，右儿子设为 $y$。
那么最后的代价就是：$\sum count_{叶子}\times dep_{叶子}$。
引理：数量最少的两堆果子堆一定是深度最大的。
显然。
如果深度最小的两堆不是最少的两堆，把最少的换过去答案一定更优。
而两个果子堆合并后形成了新的果子堆，这新的果子在后续的操作独立，后续操作同理即可。
根据数学归纳法，可得最后的 $\sum count_{叶子}\times dep_{叶子}$ 为最小值。
这一棵树就是 Huffman 树，也称最优二叉树。
排队接水：
给定 $n$ 个人的接水时间 $t_i$，安排排队顺序使得所有人等待时间之和最小。
假设排队顺序为排列 $p_n$，令 $T_i=\sum\limits_{j=1}^i t_j$。求的即为：$\sum\limits_{i=1}^nT_i$ 的最小值。同样考虑贡献，将式子变为：$\sum\limits_{i=1}^n(n-i+1)t_{p_i}$。
$a_i=n-i+1$ 为一个递减序列，$t_{P_i}$ 递增时 $\sum\limits_{i=1}^n(n-i+1)t_{p_i}$ 最小。
这就是排序不等式：
- 对于确定的两个序列 $a_n,b_n$，满足 $a_{p_i}$ 递增，$b_{q_i}$ 递减时 $\sum a_i\times b_i$ 取得最小。
证明：
对于两个乱序序列 $a_n,b_n$，不妨考虑让 $a_n$ 升序。
若 $b_1$ 此时不是最大值，不妨令 $b_j>b_1$。将 $b_j$ 和 $b_i$ 交换，做差，得新序列和原序列相差 $a_1\times b_j+a_j\times b_1-a_1\times b_1-a_j\times b_j=a_1\times(b_j-b_1)+a_j\times(b_1-b_j)=(b_j-b_1)(a_1-a_j)\leq0$
所以可以不断换最更大的，直到把最大值放到 $b_1$。对于后续 $2-n$ 同理。
货仓选址：
给定 $n$ 个商店的坐标 $a_i$，选定一个货仓 $x$，使得 $\sum\limits_{i=1}^n|a_i-x|$ 最小。
不妨将 $a_i$ 升序，货仓的坐标即为 $a_{\lceil\frac n2\rceil}$。
引理 $1$：货仓的坐标为某个商店的坐标。
反证，若 $\forall a_i\neq x$，则 ${\exist} a_i<x\land a_{i+1}>x$，那么对于 $j<i$ 和 $j>{i+1}$ 答案不变。而对于 $a_i$ 和 $a_{i+1}$，货仓位置设置在哪事实上没有影响。所以不妨设为 $a_i$。因为这样就将待选位置缩小到 $n$ 个 $a_i$ 中。
此时，考虑特殊情况。
引理 $2$：$\sum\limits_{i=1}^n|a_i-a_1|>\sum\limits_{i=1}^n|a_i-a_2|(n>2)$。
展开：$\sum\limits_{i=2}^na_i>\sum\limits_{i=3}^na_i-a_1$，易证。
所以，$x\neq a_1$。而对于 $x=a_2$ 的情况，可以和 $x=a_1$ 的情况同样考虑（在之后的过程中 $|a_1-x|+|a_n-x|=a_n-a_1$ 为定值，所以可以消去）。
当 $n=2$ 时，$x=a_1$ 和 $x=a_2$ 结果相等；或 $n=1$ 时，$x=a_1$。（取决于 $n$ 的奇偶性，因为每次去掉 $a_1$ 和 $a_n$ 两个位置）
国王游戏：
国王有 $n$ 个大臣，每个大臣左手有 $a_i$，右手有 $b_i$。每个大臣的得分是排在他前面的人的左手之积除以他的右手。国王的左手是 $a_0$，右手是 $b_0$，求一种排队顺序使得得分最大值最小。
考虑两个相邻的人谁在前面更优。$i$ 的得分：$\dfrac{\prod\limits_{j=1}^{i-1}a_j}{b_i}$，$i+1$ 的得分：$\dfrac{\prod\limits_{j=1}^{i}a_j}{b_{i+1}}$ 。
两者消去公共部分后分别为 $\dfrac{1}{b_i}$ 和 $\dfrac{a_i}{b_{i+1}}$。
如果交换，那么消去公共部分后分别为 $\dfrac{1}{b_{i+1}}$ 和 $\dfrac{a_{i+1}}{b_i}$。
注意到：$\dfrac{a_i}{b_{i+1}}>\dfrac{1}{b_{i+1}},\dfrac{1}{b_i}<\dfrac{a_{i+1}}{b_i}$。
若 $\dfrac{1}{b_i}<\dfrac{a_i}{b_{i+1}}$，即：$a_i\times b_i>b_{i+1}$，则交换后最大值只能是 $\dfrac{a_{i+1}}{b_i}$。
而如果交换更优，那么要满足 $\dfrac{a_i}{b_{i+1}}>\dfrac{a_{i+1}}{b_i}$，即：$a_i\times b_i>a_{i+1}\times b_{i+1}$。显然，满足这个条件的一定满足前置条件。
若 $\dfrac{1}{b_i}>\dfrac{a_i}{b_{i+1}}$，即：$a_i\times b_i<b_{i+1}$，则交换后的最大值就是 $\dfrac{a_{i+1}}{b_i}$ 且不更优。所以不需要交换。
所以将大臣们按照 $a_i\times b_i$ 的值升序排队即可。
为什么只要考虑相邻两个？
因为如果队伍不是按 $a_i\times b_i$ 有序的，那么就一定会有两个相邻的人满足 $a_i\times b_i>a_{i+1}\times b_{i+1}$，而调整它，就会更优。所以一定会调整至 $\forall a_{i}\times b_i<a_{i+1}\times b_{i+1}$。
反悔贪心：
在一般贪心中，通常为得出一个策略，按照策略即可直接得到答案。而有的时候，结合以往的结果去对修正当前的决策也是可以的，但是从宏观上看，还是“贪心”的。对于这种贪心，一般被称为反悔贪心（也有说法细分为反悔堆和反悔自动机）。
任务安排：
给定 $n$ 个任务，对于每个任务都有一个截止日期（$\leq 10^9$）和完成价值。从第一天开始，每天可以选择一个任务完成。求能获得的最大价值。
对于两个不同截止日期的任务，一定是先完成截止早的，显然。
对于两个相同截止日期的任务，一定是先完成价值大的，显然。
所以先将任务按截止日期升序，但是时间范围过大，不允许枚举模拟。
考虑反悔贪心：
若在某一天发现一个价值很大没有选择的任务，但是任务安排已经超过这天了。这时，我们反悔了。所以要去掉一个已经选择的中最小的一个，替换成这个价值大即可。
所以用一个优先队列维护已经选择的任务， 由于任务总数不大，所以最终时间复杂度为：$O(n\log n)$。
使用堆维护类似的过程，也被部分人称作反悔堆。
种树：
共有 $n$ 个坑可以种树，且每个坑种树后能获利 $a_i$，但要求不能有两棵树相邻。求种 $k$ 棵树最大获利。
若无不能相邻的限制，则直接选取前 $k$ 大即可。
考虑有什么区别，不能相邻，每次有两种情况：
- 在不相邻的位置中，选择一个最大值，贡献即为 $a_j$。
- 选择一个相邻的位置但是要把当前这棵树给挖掉，所以贡献为 $a_{i+1}-a_i$ 或者 $a_{i-1}-a_i$。可是如果 $a_{i+1}-a_i>0$ 或者 $a_{i-1}-a_i>0$ 的话，那么 $a_{i+1}$ 或者 $a_{i-1}$ 会在之前就被考虑，所以不能选择左右之一，只能是 $a_{i+1}+a_{i-1}-a_i>0$ 即相邻的同时选。
所以，每次贪心在未被选择的 $a_1,..,a_{i-2},a_{i+2},…,a_n$ 和 $a_{i+1}+a_{i-1}-a_i$ 中选择一个最大值。
若选择的是 $a_{i+1}+a_{i-1}-a_i$，那不能再选的是 $a_{i+2}$ 和 $a_{i-1}$。所以我们用一个新建节点来表示 $a_{i+1}+a_{i-1}-a_i$ 且用它来替代原本 $i$ 的位置，使用双向链表维护相邻元素，并标记相邻元素不能被选（如果同一个点被选三次，那么它本身的贡献会重新变成正的，此时便蕴含着反悔的含义）。
共选择 $k$ 次最大值。
上述过程也被部分人称之为反悔自动机。