贪 心

杂谈

贪心就是贪心，比如说我现在说深海色是我的老婆，就表明我在当前状态下想要选择深海色作为老婆，很显然这对于我来说是一个当前状态下最优的决策，所以深海色是我老婆我进行的操作是贪心。

定义

贪心是一种在每次决策时采取当前意义下最优策略的解法，因此，使用贪心法要求问题的整体最优性可以由局部最优性导出。

在对一道题使用贪心算法时，其正确性需要被证明。

方式

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

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

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

不懂的话，上几道题就明白啦！

Sunscreen

奶牛由两个防晒程度值 $minspf$ 和 $maxspf$，由 $L$ 种 $spf$ 不一样的防晒霜各有一定数量的瓶数。
要求防晒霜的 $spf$ 的值大于奶牛的 $minspf$ 且小于 $maxspf$，问这些瓶数的防晒霜能最多能保护多少奶牛。

我们是否可以知道某些情况下使用防晒霜对应一头奶牛一定是正确的呢？

答案是肯定的。

我们可以按照 $minspf$ 递减的顺序把奶牛排序，依次考虑每头奶牛.

对于每头奶牛，扫描一遍所有防晒霜，在这头奶牛能用的防晒霜里找 $spf$ 值最大的使用。

设 $SPF_X<SPF_Y$,如果当前奶牛都可以用，那么后面的奶牛只能有三种情况：

1.$X$ 和 $Y$ 都可以用。

2.$X$ 可以用，$Y$ 不能用。

3.$X,Y$ 都不能用。

那么可以选 $Y$ 的影响比选 $X$ 的小，同时带来的效益都是 1，所以没有区别。

Stall Reservations

给出 $n$ 个区间，第 $i$ 个区间表示为 $[l_i,r_i]$，询问把这些最少的分组数，使得每组内每个区间相离，$1\leq N\leq5\times 10^4$。

区间问题，首要考虑排序，因为涉及分组，于是得保存组的信息，不妨设 $a_i$ 为分的第 $i$ 组的最后一个区间的右端点。

现在来考虑第 $i$ 个区间的决策点，对于能分进的组 $j$，必然是 $a_j<l_j$，第 $i$ 个区间才能被分进去，但是选哪一个组，按照朴素的思想，必然是选 $a_j$。

最小的或者最大的，因为是按左端点排序，后面的区间左端点必然增大，于是前面区间能分进的组，后面的区间也能分进，于是无论选哪一个组都无所谓，如果不能选，必然要新开一个组。

现在的问题是如果能分进一个组，会不会开一个新组让结果更加优秀，此时微扰法就不好证明了，于是采取决策包容，注意到新开一个组，它能够选择的范围只有第 $i$ 个区间所包含的位置，而不新开一个组，以后新开一个组，与它同等优秀，但是组的最后一个区间的右端点可以是任意一个区间的右端点，于是后者决策包含前者决策，选后者一定不会差，得证。

Radar Installation

雷达有一个半径 $R$，在笛卡尔坐标系的 $x$ 轴上安置雷达，使雷达可以覆盖 $x$ 轴及其上方的若干个岛屿，要求最少使用的雷达数。

处理各点需要雷达位置的范围 $[x-sqrt(d^2-y^2),x+sqrt(d^2-y^2)]$，然后对所有范围的下界从小到大排序，这样可以通过各范围的上界来找出重叠的范围，所有重叠的区域都可以用一个雷达来囊括所有的小岛。

要注意的就是对于输入的雷达探测半径如果小于 0，或者小岛的位置在陆地上 $(Y<0)$，都要特殊判断。

国王游戏

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

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

由上面这张表格可以知道这样的情况时：

第一个人所得的金币数为 $\frac{X_1}{R_1}$；

第二个人所得的金币数为 $\frac{X_1\times L_1\times X_2}{R_2}$；

所以最小值为 $\max(\frac{X_1}{R_1},\frac{X_1\times L_1\times X_2}{R_2})$；

然后交换两个人的位置：

由上面这张表格可以知道这样的情况时：

第一个人所得的金币数为 $\frac{X_1\times L_2\times X_2}{R_1}$；

第二个人所得的金币数为 $\frac{X_1}{R_2}$；

所以最小值为 $\max(\frac{X_1\times L_2\times X_2}{R_1},\frac{X_1}{R_2})$；

综合上面两种情况：

如果变换之前的情况要优于变换之后的情况，那么

$\max(\frac{X_1}{R_1},\frac{X_1\times L_1\times X_2}{R_2})<\max(\frac{X_1\times L_2\times X_2}{R_1},\frac{X_1}{R_2})$

而 $\frac{X_1}{R_1} < \frac{X_1\times L_2\times X_2}{R_1}$ 恒成立；

$\frac{X_1\times L_1\times X_2}{R_2} < \frac{X_1}{R_2}$ 同理；
所以上述条件成立时

必须有 $\frac{X_1\times L_1\times X_2}{R_2} < \frac{X_1\times L_2\times X_2}{R_1}$ 恒成立；所以化简可得 $L_1\times R_1 < L_2\times R_2$ 恒成立。

记得打高精

总结

贪心的思想就是只要这是当前最好的就无脑进行当前决策，由此来更快速地得到较优甚至最优的解。