贪心算法小结

写在前面

在信息学竞赛中有一类常用的算法,叫做贪心算法。所谓贪心,即对于当前的每一步决策都考虑选择最优的分支,从而使得整体最优,而对于一个问题划分成N个决策,在每次决策中选择最优的分支所需要的时间可以采用堆、左偏树、优先队列等实现(也有根据决策无需修改,在开始进行一次排序即可),进而将问题的时间复杂度大大缩减为O(NlogN)以内。贪心算法无疑是解决问题比较完美的方法,但他的局限在于无法顾及到全局,由于每次只考虑最优决策的局限性,贪心算法容易走入较差解乃至最差解的深坑中,所以在使用贪心算法前需要有对于算法正确性的严(bao)格(li)证(dui)明(pai)。笔者因为贪心学得不好,所以来补这篇文章,用于给自己做总结,希望高手能够指正文中的错误,不胜感激。

贪心的正确性的证明

我们从贪心的正确性的证明入手,大部分情况我们所采用的都是反证、拟阵等,后者不加以赘述。可以参考花神的论文。我们着重讲反证法,先来看一道例题。

Example 1. [Codeforces 667B] Coat of Anticubism

题目大意:给出n\leq 1e5个木棍,每个的长度为l_{i},保证一开始这些木棍不能组成凸多边形,现在让你加入一根木棍,在可以组成凸多边形的情况下最小化加入木棍的长度。

关于本题的结论是:将最大的那条边单独分为一组,剩下的所有边分成两组,不妨记为c,a,b,由题意可知c\geq a+b(不妨考虑为三角形)而此时为了使得这个不等式狗带,我们需要一个\delta,满足c<a+b+\delta,于是可以推算得知答案即为c-a-b-1

证明:该结论成立的前提在于假设为三角形,那么不妨推翻,令之为n(n>3)边形,但是我们发现,多出来的那些边,一定可以通过移动而变成三角形,由三角形三边等价性可知任意情况均可回到题设中,故此前提成立,而由成立的前提推出的成立的答案即为正确答案,证毕。

这个例子其实并不算作完整的反证法,因为他只用到了对于逆命题的等价变换而与原命题重合,从而推出逆命题不存在,进而证明原命题的成立性。


Example 2. 最短路径性质的证明(dijkstra)

众所周知,最短路比较常用的算法有spfa,dijkstra(一般都会堆优化),而dijkstra的依据则是贪心,我们来对它进行一番证明!

dijkstra所用到的贪心是在于最短路径性质,即假设s->s_{1}->...->s_{k}->t是一条合法的最短路径,那么其中的一个子区间[l,r],就是lr的最短路。

证明:假设存在[l,r]满足s_{l}->s'_{l+1}->s'_{l+2}->...->s_{r}\;<\;s_{l}->s_{l+1}->s_{l+2}->...->s_{r}

那么从st的最短路即可更新为s->s_{1}->...->s_{l}->s'_{l+1}->...->s_{r}->...->t,与原命题s->s_{1}->...->s_{k}->t是最短路矛盾,故假设不成立,原命题成立,证毕。

这里所采用的就是原汁原味的反证法了,通过假设一种否定当前贪心结论的结论的推翻来证明当前贪心结论不存在错误。


感性贪心

对于贪心问题的解决,无非几个步骤

(1)发现题目的规模很大,动态规划无法解决

(2)对于问题进行阶段划分,如NOIP旅行家的预算中,以油箱的库存为阶段进行划分

(3)明确对于每个阶段的决策的特征,构思最优决策的性质

(4)列出贪心结论,采用反证、拟阵、对拍等方法对其进行证明。考场上可跳过

(5)计算出整体时间复杂度,对于每次决策如果过慢则采用数据结构进行维护

(6)完善细节

那么我们要说的感性贪心就是可以省略(2)(3)(4),从(1)直接跳到(5)的贪心算法。

Example 3.[Australian Informatics Olympiad 2015, senior] Ruckus League

题目大意:有N(N\leq 1e5)个小朋友,第i小朋友的右手握着第a[i]个小朋友的左手,你每次可以花一根棒棒糖来让某个小朋友放手,你总共有K根棒棒糖,问最多能将小朋友们分成多少组(要求每一组人数不得低于M)。(对于组的定义你可以看做是一个连通块)

考虑到数据范围异常的大,我们采用贪心的思路

先进行建模,把小朋友抽象成点,把右手握左手抽象成一条无向边

那么很容易发现,对于这种图,一共只可能有两种情况:环,链

而发现,对于环想要把它切成2块及2块以上的话,至少要花2根棒棒糖

而链只需要1根,显然就先把链进行切割,再考虑环

对于链的切割,考虑尽可能分m个人一组,因为这样最省棒棒糖

环只需要断成链再切即可

对于链我们没有特殊的要求,而环的话,需要考虑大小

为什么呢?因为对于一个环,你要花一根棒棒糖来把它破坏,而如果你把它破坏以后发现他并没有你想象的那么优(比如说只能分成2组),我们不如不破坏,所以这就需要对环的大小进行排序,再进一步切割。

判链or环采用并查集,于是总的时间复杂度为O(n\alpha(n)+n\log n)

关于此题的方法,还有一个姐妹题,见例题4


Example 4.[bzoj 1124][POI2008] 枪战

题目大意:有n个人,每个人手里有一把手枪。一开始所有人都选定一个人瞄准(有可能瞄准自己)。然后他们按某个顺序开枪,且任意时刻只有一个人开枪。因此,对于不同的开枪顺序,最后死的人也不同,求最多死多少人,最少死多少人。

和例三一样,对题目进行建模,这样我们就转化为一些基环树和环。

先考虑最少死多少人

对于基环树内,隔一个杀一个是最好的

对于环内,也同样是隔一个杀一个

考虑最多死多少人

对于环内,倒着杀,只有第一个人能苟活

对于基环树,只有没有被瞄准的人能苟活

判环同样采用并查集


带修改的贪心

很多时候我们对于当前点的决策可能会影响到后续点,而这个时候可能我们就认为无法贪心,必须得采用动态规划之类的,而动态规划又束手无策,怎么办呢?贪心其实是可以带修改的!

Example 5.[bzoj 1029][JSOI2007] 建筑抢修

题目大意:有N(N\leq 1e5)个建筑,每个建筑有一个最迟被修理完时间,以及修理需要的时间,问在T时间内最多能修多少建筑

一脸背包的感觉,然而我们发现是最迟修理时间,所以无法进行动态规划

那么来考虑贪心

很直观的想到,我们把建筑按照最迟被修理完时间从小到大排序

越小的肯定优先选择修理

但是这里就要有个问题,如果出现了当前扫描到的建筑修不起来,但是用这个建筑替换某一个已经修好的建筑能使得当前的总时间更优的话,不如就拿它替换。

于是我们对于贪心的修改就是:每次找出已经选择的点中最大的需要修理时间,用新建筑替换掉它(前提是删掉它后新建筑可以建成),这个过程可以用优先队列来实现,总的复杂度O(n\log n)


Example 6.[bzoj 1150][CTSC2007] 数据备份

题目大意:有N个城市间需要插K条电缆,每条电缆只能连接相邻的两个城市,最小化电缆总长度。

先考虑对给出的距离进行差分,问题就转化为从N-1个数中选K个数使得他们互不相邻,最小化他们的总和。

很容易想到贪心,但是容易出现一个问题,一昧的选最小的不相邻的数,容易挂掉,因为肯定会有选大的反而合适的时候,那么我们不妨类似网络流的残余网络一样,给贪心构造退路

对于每次插入一个点,我们考虑删除它,它左边,它右边,加入他左边加右边减去他的权。

这样每次选加入的等价于取消了这步操作。贪心便有了后路!


常用的套路

贪心还可以被放在树上,而面对这类问题,我们对树进行一次遍历,每次回溯的时候对当前子树进行贪心即可。

而面对答案无法直接算出来,必须要枚举的时候,我们可以采用二分或者三分答案的方法,来加速枚举。

Example 7.[bzoj 2097][Usaco2010 Dec] 奶牛健美操

题目大意:给一棵树,最多可以删除S条边,最小化最后剩余的所有树的直径的最大值

最小值最大,很容易想到二分直径

考虑对于答案的验证,我们从所有的子树考虑,对于每一棵当前最小的子树,他的直径一定过根(为什么?后面会解释),于是把和他相连的边从大到小排序,依次删除,最后无法保留的上传给父亲节点,这样也能保证父亲的直径一定是过根的。


Example 8.[bzoj 4027][HEOI2015] 兔子与樱花

题目大意:给出一棵树,你每次可以删除一个点,删除该点以后,该点的儿子上的樱花数会累加到该点的父亲上,该点的儿子分支也全会接到父亲上,问在满足所有点的节点樱花数+节点儿子个数\leq m的前提下,最多能删除多少个点。

考虑对于每个节点删除的代价,等价于该节点樱花数+该节点儿子数

那么对于这个代价进行排序,从小到大选择,用DFS维护即可


总结

贪心的境界在于能够深刻理解当前所需要求的值,以及怎样局部最优。在一些复杂的题目中,往往能发挥巨大作用,所以我还是要多练啊QWQ

发表评论