贪心

定义

贪心算法适用于最优子结构问题。意思是问题在分解成子问题来解决时，子问题的最优解能递推到最终问题的最优解。常见的符合这种性质的问题如：

• 「我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从小到大）选择。」
• 「我们每次都取 XXX 中最大/小的东西，并更新 XXX。」

但比如在大部分只能用动规求解的问题上，贪心算法目光短浅的后果就是答案错误（如石子合并）。所以碰到动规题目以为有贪心做法时最好三思有无反例。

而在考场实际运用贪心时通常都是感性证明，但其实严格证明贪心的话会使用 反证&归纳法 进行推导。

过程

一般我们会有两种解法：邻项交换&反悔贪心 。

• 前者一般可以用反证法，证明出交换方案中相邻元素后答案不优后，将最终状态通过定义 \(cmp\) 函数简单 \(sort\) 比较后得出。比如常见的「性价比」就是典例。
• 后者分为人工模拟和自动策略，都要求在发现亏损后及时反悔，将当时错误决策撤回，而这个“错误决策”在需人工模拟的问题中常常对应为已作选择中最XXX的一个，使用堆优化。或者制定一个完全的策略，使得程序对特情自动处理，执行反悔策略。一般需要通过做差巧妙达成目的。

应用

主要归纳典型贪心例题及方法：

货币支付

用最少的基本货币凑出指定金额

能用大钞就先用大钞，直到只剩零头了再换小钞。

区间分配

每个位置都有容量。在给出的所有区间中选出尽量多的区间，使得每个位置被覆盖总数不超过容量

将区间按右端点从左到右，左端点从右到左排序，贪心选择，区间减一用线段树维护。特殊地，容量为1时排序后直接选即可。例：公平班车、牛舍分配等。

任务调度

每个任务都有时限和代价。求一种安排使得能在对应时限前完成的任务总数最多

每个任务都有时限和利润。求一种安排使得能在对应时限前完成的任务利润最大

维护一个 已选任务的堆 和 所用时间/所得利润，按时限先后排序，贪心选择能做的任务。没得选就把已选中 最耗时的/最不赚的 踢掉。因为已按时限排序，故而保证了删除一个后就一定符合时限条件了。其实这是一种典型的“性价比”思想。例：工作调度、建筑抢修等。

选坑种树

在一条路上有 \(n\) 个坑可以种树。每个坑有其美观度，但土壤肥力有限，不能连续种树。给出 \(m\) 棵要种的树，求最美丽的种植方案。

反悔贪心的一种典型解法：在直接选择最赚的坑种下一棵树后可能不如选旁边两个优，故而维护一个记录左右相邻的坑位的双向链表和一个记录未选坑位的美观度的堆。每次选大根堆的根并将它及其左右标记为不可种。然后 将左右邻点权值和减去已选点权值后作为新点权值，将新点插回原来三点位置 。这就是一个自动贪心策略了。例：种树（环）、种树（链）、数据备份（点转线段）等。

如上例，选 \(7、7\) 一定比 \(1、2、9\) 更优。但是我们贪心选得了 \(9\)。为了留下反悔余地，我们新开一个权值为 \(7+7-9=5\) 的点代替 \(7、9、7\) 三点：

这样，我们自然又选得了5。

至此，所有点选完，算法结束。

复盘一下，不难发现人工选择 \(7、7\) 与自动选择 \(9、5\) 的结果是不变的，因为对于连续三点 \(a、b、c\)，选 \(b\) 后插入了 \(a+c-b\)。一旦后面反悔，\(b+(a+c-b)=a+c\)，不就等效于选了 \(a、b\) 了吗。且得益于双向链表，最后每个点的可选状态（以黑白区分）也相同，所以这种做法可以扩展开来，在两边继续加长甚至形成一个环。

股票买卖

给出每天股票价格。每天你可以买进一股股票，卖出一股股票，或者什么也不做。\(n\) 天之后卖出所有股票，使得这 \(n\) 天内赚的钱最多。

对于每一个形如「在第 \(i\) 天买入，在第 \(j\) 天卖出」的决策，假想出一股第 \(j\) 天的克隆股票，使得支持「在第 \(i\) 天买入，在第 \(j\) 天卖出，同时买入这个虚拟股票，并在第 \(k\) 天卖出」的操作，因为第 \(j\) 天卖出后立马选择买入，等价于「在第 \(i\) 天买入，在第 \(k\) 天卖出」了。\(j\) 反悔成 \(k\) 的操作得以实现。

于是，我们便设计出了一个新的算法：维护一个可重集合，代表「可选股票的价格」。从前向后遍历每一天，对于第 \(i\) 天，向集合中插入 \(price_i\)，代表 \(price_i\) 这一股可选。再找到集合中最小的价格 \(price_j\)，若 \(price_i>price_j\) 就有的赚。贪心选择「在第 \(j\) 天买入，在第 \(i\) 天卖出」，把答案加上 \(price_i−price_j\)，并向集合中再次加入 \(price_i\)，代表假想的反悔股票，并将 \(a_j\) 从集合中删除。我们可以使用堆维护这个集合。