贪心

定义

贪心算法，又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

理解

贪心，就是用计算机来模拟一个「贪婪」的人做出决策的过程。
在解决问题的过程中，每一步行动总是在当前已有条件下，按某种指标选取最优的操作，并不考虑以后可能造成的影响。
可想而知，在这种策略下，并不是所有的情况贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保能证明其正确性，即证明最终能获得最优解。

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

贪心策略

这里介绍两种常用的贪心策略：

1. 将元素按照某某顺序排序，然后按某种顺序（例如从小到大）遍历排好序的序列完成计算。
2. 将所有未被选择的元素都放在一个集合中，每次都按照某种指标取集合中最大/小的东西，并更新集合。（为了快速获取集合中的最大/最小，可以用特定数据结构维护集合，例如优先队列。）

二者的区别在于一种是离线的，先处理（即排序）后选择；一种是在线的，边处理（动态维护）边选择。

证明方法

在使用贪心法求解问题时，需要证明其正确性。这里介绍一种常用的证明方法：邻项交换法。

邻项交换法

证明在任意局面下，任何对局部最优策略的微小改变都会造成整体结果变差。换句话说，如果交换任意两个相邻元素，整体结果会变差，则证明当前采用的局部最优策略可以保证达到全局最优解。

具体应用

国王游戏

恰逢 $H$ 国国庆，国王邀请 $n$ 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个正整数，国王自己也在左、右手上各写一个整数。然后，让这 $n$ 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

贪心策略：按照每个大臣左、右手上的数的乘积从小到大排序。这一贪心策略的正确性可以用邻项交换法证明。

对于任意一种排列顺序，设第 $i$ 位大臣左、右手上的数分别为 $A[i]$ 和 $B[i]$，国王手上的数为 $A[0]$ 和 $B[0]$。
不失一般性，考虑相邻的两位大臣 $i$ 和 $i+1$ 进行交换。
在交换之前，这两位大臣获得的奖励分别为 $\frac{1}{B[i]} * \prod_{j = 0}^{i - 1} A[j]$ 和 $\frac{A[i]}{B[i + 1]} * \prod_{j = 0}^{i - 1} A[j]$。
在交换之后，这两位大臣获得的奖励分别为 $\frac{1}{B[i + 1]} * \prod_{j = 0}^{i - 1} A[j]$ 和 $\frac{A[i + 1]}{B[i]} * \prod_{j = 0}^{i - 1} A[j]$。
显然，交换前后其他大臣获得的奖赏都不变，因此只需比较交换前后以上两组式子哪个更优（即获得奖赏最多的大臣，所获奖赏尽可能的少），也就是比较以上两组式子中的最大值哪个更小。
提取公因式 $\prod_{j = 0}^{i - 1} A[j]$，由于大臣左右手上的数都是正整数，因此公因式不会为 $0$，可以消除，则只需要比较 $\max(\frac{1}{B[i]}, \frac{A[i]}{B[i + 1]})$ 和 $\max(\frac{1}{B[i + 1]}, \frac{A[i + 1]}{B[i]})$ 哪个更小。
两边同时乘上 $B[i] * B[i + 1]$，变为比较 $\max(B[i + 1], A[i] * B[i])$（设为 $\textcircled{1}$）和 $\max(B[i], A[i + 1] * B[i + 1])$（设为 $\textcircled{2}$）哪个更小。
由于大臣左右手上的数都是正整数，则 $B[i] \leq A[i] * B[i]$ 并且 $B[i + 1] \leq A[i + 1] * B[i + 1]$。
因此可以分情况讨论，如果 $A[i] * B[i] \leq A[i + 1] * B[i + 1]$，则 $\textcircled{1} \leq A[i + 1] * B[i + 1] \leq \textcircled{2}$，$\textcircled{1}$ 式更优，即交换之前更优。如果 $A[i] * B[i] \geq A[i + 1] * B[i + 1]$，则 $\textcircled{2} \leq A[i] * B[i] \leq \textcircled{1}$，$\textcircled{2}$ 式更优，即交换之后更优。
结合这两种情况的分析可以发现，相邻的两位大臣在进行排列时，左右手上的数乘积小的大臣，应该站在靠前的位置，而乘积大的大臣，应该站在靠后的位置，否则只会使整体结果更差。
要保证任意两个相邻的大臣，位置靠前的左右手上的数乘积小，根据冒泡排序的知识，任何一个序列都能通过邻项交换的方式变为有序序列，因此只需要按照每个大臣左、右手上的数的乘积从小到大排序，所得序列就是最优策略。

合并果子

现在有 $n$ 堆果子，第 $i$ 堆果子的重量为 $a_i$。每一次可以选择两堆不同的果子进行合并，耗费的力气就是这两堆果子的重量之和。

问最少需要多少耗费多少力气才能使得这 $n$ 堆果子最终合成一堆？

很显然，合并了两堆果子之后，虽然看起来它们已经成为了一堆果子，但是在计算最终耗费的力气时，仍然是按照原始重量计算的。
由于有 $n$ 堆果子，所以一共需要合并 $n - 1$ 次，那么肯定存在一堆果子正好合并 $n - 1$ 次，也有一堆果子只合并了 $1$ 次。为了让答案最小就需要把 $a_i$ 较大的果子尽量少合并，$a_i$ 较小的果子尽量多合并。这样最后的答案就也是最小的。
因此，在每次合并时，要选择重量最小的两堆进行合并，并累计耗费的力气，合并完成后还要将合并得到的新的一堆果子作为一个新的堆与剩余的果子比较重量，再找到重量最小的两堆重复操作。
这里就用到了第二种贪心策略，使用优先队列（最小堆）维护果子中的最小重量。