0x07贪心

贪心是一种在每次决策时采取当前意义下最优策略的算法，因此，使用贪心法要求问题的整体最优性可以由局部最优性导出。贪心算法的正确性需要证明，常见的证明手段有：

1. 微扰（邻项交换）

证明在任意局面下，任何对局部最优策略的微小改变都会造成整体结果变差。经常用于以“排序”为贪心策略的证明。

2. 范围缩放

证明任何对局部最优策略作用范围的扩展都不会造成整体结果变差。

3. 决策包容性

证明在任意局面下，作出局部最优决策以后，在问题状态空间中的可达集合包含了作出其他任何决策后的可达集合。换言之，这个局部最优策略提供的可能性包含其他所有策略提供的可能性。

4. 反证法

5. 数学归纳法

我们通过几道例题来介绍贪心算法的应用。

【例题】Sunscreen POJ3614

有 $C$ 头奶牛日光浴，第 $i$ 头奶牛需要 $\min\mathrm{SPF}[i]$ 和 $\max\mathrm{SPF}[i]$ 单位强度之间的阳光。每头奶牛在日光浴前必须涂防晒霜，防晒霜有 $L$ 种，涂上第 $i$ 种之后，身体接收到的阳光强度就会稳定为 $\mathrm{SPF}[i]$ ，第 $i$ 种防晒霜有 cover[i] 瓶。求最多可以满足多少头奶牛进行日光浴。 $C, L \leq 2500$ 。

按照minSPF递减的顺序把奶牛排序，依次考虑每头牛。

对于每头牛，扫描一遍所有的防晒霜，在这头牛能用（能用指的是该防晒霜的强度符合这头牛的范围，并且瓶数还有剩余）的防晒霜里找一个SPF值最大的防晒霜使用。

以上算法的贪心策略是在满足条件的前提下每次选SPF最大的防晒霜。这个策略为什么是正确的呢？我们考虑这一步策略的作用范围扩展到后续其他奶牛之后产生的影响。每瓶防晒霜是否可用，会被minSPF与maxSPF两个条件限制。因为奶牛已被按照minSPF递减排序，所以每一个不低于当前奶牛minSPF值的防晒霜，都不会低于后面其他奶牛的minSPF。也就是说，对于当前奶牛可用的任意两瓶防晒霜 $x$ 与 $y$ ，如果 $\mathrm{SPF}[x] < \mathrm{SPF}[y]$ ，那么后面其他奶牛只可能出现“ $x, y$ 都能用”“ $x, y$ 都不能用”或者“ $x$ 能用， $y$ 不能用”这三种情况之一。因此当前奶牛选择maxSPF较大的 $y$ 去使

用，对于整体问题的影响显然比选择maxSPF较小的 $x$ 更好。

另外，每头奶牛对答案的贡献至多是1。即使让当前这头奶牛放弃日光浴，留下防晒霜给后面的某一头奶牛用，对答案的贡献也不会变得更大。综上所述，尽量满足当前的奶牛，并选择SPF值尽量大的防晒霜是一个正确的贪心策略。

【例题】StallReservations FOJ3190

有 $N$ 头牛在畜栏中吃草。每个畜栏在同一时间段只能提供给一头牛吃草, 所以可能会需要多个畜栏。给定 $N$ 头牛和每头牛开始吃草和结束吃草的时间, 每头牛在给定时间段内会一直吃草, 求需要的最小畜栏数目和每头牛对应的畜栏方案。 $N \leq 5 * 10^{4}$ 。

按照开始吃草的时间把牛排序。

维护一个数组 $S$ ，记录当前每个畜栏安排进去的最后一头牛，最初没有畜栏。

依次对于每头牛，扫描数组 $S$ ，找到任意一个畜栏，满足当前的牛开始吃草的时间不早于畜栏中最后一头牛结束吃草的时间。如果这样的畜栏不存在，则为其新建一个畜栏。

这个贪心算法的时间复杂度是 $O(N^{2})$ ，请读者自行证明其正确性。我们可以用一个小根堆（STLpriority_queue）维护每个畜栏最后一头牛结束吃草的时间，尝试把当前的牛安排在堆顶（结束时间最早）的畜栏中。这样时间复杂度就可以降低到 $O(N\log N)$

【例题】Radar Installation FOJ1328

校长想通过监控设备覆盖学校内的 $N$ 座建筑物，每座建筑物被视作一个质点，在笛卡尔坐标系中给出它们的坐标 $(x, y)$ ，并且所有建筑物均处在 $x$ 轴的上方。因为学校的供电和传输线路均沿 $x$ 轴，所以监控设备只被允许建立在 $x$ 轴上。每台监控设备的监控范围均为一个半径为 $R$ 的圆形，圆心即为这台设备。现给出 $N$ 座建筑物的坐标，问最少需要几台这样的设备可以实现对所有建筑物的监控？ $N \leq 1000$ 。

对于 $x$ 轴上方的每个建筑物，可以计算出 $x$ 轴上的一段能管辖它的区间 $l[i] \sim r[i]$ 。问题转化为：给定 $N$ 个区间，在 $x$ 轴上放置最少的点，使每个区间包含至少一个点。

按照每个区间的左端点 $l[i]$ 从小到大排序，用一个变量维护已经安放的最后一台监控设备的坐标pos，起初pos为负无穷。

依次考虑每个区间。如果当前区间 $i$ 的左端点 $l[i]$ 大于最后一台监控设备的坐标 $pos$ ，则新增一台设备，令 $pos = r[i]$ 。否则就让最后一台已经安放的监控设备来管辖当前区间，并令 $pos = \min(r[i], pos)$ 。

依此类推，直至所有区间被管辖，输出安放的设备个数即可。

这个贪心算法可以用“决策包容性”来证明。

首先，对于每个区间 $l[i]\sim r[i]$ ，有两种选择：

1. 使用已有的监控设备管辖它。

2. 新建一台监控设备管辖它。

我们的贪心策略是，当选择1可行时，不会选择2。选择1之后，未来可以在任意位置新建一台监控设备，而选择2则需要在 $l[i] \sim r[i]$ 之间新建设备，也就是说，第1项选择未来可能到达的状态包含了第2项选择未来可能到达的状态。

其次，在选择1之后，我们把上一台设备调整到 $\min (r[i],pos)$ 的位置，也就是在能管辖 $i$ 的前提下尽量往后放，“尽量往后放”这个策略未来的可达状态显然也包含了“放在更靠前的位置”未来的可达状态。最后，因为所有区间已经按照 $l[i]$ 排序，所以这个调整不会影响到已经被管辖的区间，证毕。

【例题】国王游戏 NOIP2012/CODEVS1198

恰逢H国国庆，国王邀请 $n$ 位大臣来玩一个有奖游戏。首先，他让每位大臣在左、右手上面分别写下一个正整数，国王自己也在左、右手上各写一个正整数。然后让这 $n$ 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能地少。注意，国王的位置始终在队伍的最前面。

按照每个大臣左、右手上的数的乘积从小到大排序，就是最优排队方案。这个贪心算法可以使用微扰（邻项交换）证明。

对于任意一种顺序，设 $n$ 名大臣左、右手上的数分别是 $A[1] \sim A[n]$ 与 $B[1] \sim B[n]$ ，国王手里的数是 $A[0]$ 和 $B[0]$ 。

如果我们交换两个相邻的大臣 $i$ 与 $i + 1$ ，在交换前这两个大臣获得的奖励是：

交换之后这两个大臣获得的奖励是：

其他大臣获得的奖励显然都不变，因此我们只需要比较上面两组式子最大值的变化。提取公因式 $\prod_{j=0}^{l-1} A[j]$ 后，实际上需要比较下面两个式子的大小关系：

两边同时乘上 $B[i]*B[i + 1]$ ，变为比较：

注意到大臣手上的数都是正整数，故 $B[i + 1] \leq A[i + 1] * B[i + 1]$ ，且 $A[i] * B[i] \geq B[i]$ 。

于是，当 $A[i]*B[i]\leq A[i + 1]*B[i + 1]$ 时，左式 $\leq$ 右式，交换前更优。当 $A[i]*B[i]\geq A[i + 1]*B[i + 1]$ 时，左式 $\geq$ 右式，交换后更优。也就是说，在任何局面下，减小逆序对数都不会造成整体结果变差，而增加逆序对数则不会使整体结果变好。

最后，根据冒泡排序的知识，任何一个序列都能通过邻项交换的方式变为有序序列。故当逆序对数为0，即按上述方案排序时就是最优策略。

【例题】ColoraTreePOJ2054

一棵有 $n (1 \leq n \leq 1000)$ 个节点的树，每个节点 $i (1 \leq i \leq n)$ 都有一个权值 $A[i] (1 \leq A[i] \leq 1000)$ 。现在要把这棵树的节点全部染色，染色的规则是：根节点 $R$ 可以随时被染色；对于其他节点，在被染色之前它的父亲节点必须已经染上了色。每次染色的代价为 $T * A[i]$ ，其中 $T$ 代表当前是第几次染色。求把这棵树染色的最小总代价。

有一个错误的贪心算法是“每一步在可以被染色的点里选权值最大的染色”，读者很容易构造出其反例——只要构造一棵树，让一个权值很小的节点下边有很多权值巨大的节点，另一个权值较大的节点却没有子节点。

不过从这个错误的贪心算法的思考中，我们可以提取出一个正确的性质：树中除根节点外权值最大的点，一定会在它的父节点被染色后立即染色。

于是我们可以确定的是，树中权值最大的点及其父节点的染色操作是连续进行的，我们可以把这两个点“合并起来”。合并得到的新点的权值设为这两个点的权值的平均值。

例如有权值为 $x, y, z$ 的三个点，我们已知 $x$ 和 $y$ 的染色操作是连续进行的，那么就有两种可能的染色方案：

1. 先染 $x, y$ ，再染 $z$ ，代价是 $x + 2y + 3z$ 。

2. 先染 $z$ ，再染 $x, y$ ，代价是 $z + 2x + 3y$ 。

我们主要关心这两个代价之间的大小关系，所以不妨把两个式子同时加上 $(z - y)$ 再除以2，分别得到：

1. 代价 $(x + y) / 2 + 2 * z$ 。

2. 代价 $z + 2 * ((x + y) / 2)$ 。

这恰好就相当于有权值为 $(x + y) / 2$ 和 $z$ 的两个点的两种染色次序。换言之，下

列两种情况的“最优染色次序”可以互相转化：

1. 权值为 $x, y, z$ 的三个点。

2. 权值为 $(x + y) / 2$ 和 $z$ 的两个点。

进一步推进，我们可以得到一种“等效权值”的算法：记录每个点是由多少个点合并而成的，一个点的“等效权值”定义为：

该点包含的原始权值总和 $\div$ 该点包含的原始点数

根据一开始提到的性质，我们不断在树中取“等效权值”最大的点 $p$ ，与其父节点 $fa$ 合并。合并之前 $p$ 与 $fa$ 各自包含的点的染色顺序是已知的，我们就让 $p$ 中第一个点排在 $fa$ 中最后一个点之后紧接着被染色，把这个顺序保存在 $p$ 与 $fa$ 合并以后的点上。最终整棵树合并成一个点后，我们就按照这个点内保存的顺序在原始的树上把各个节点依次染色，计算出花费的总代价，即为所求。