国家集训队2008论文集部分贪心在信息学竞赛

部分贪心在信息学竞赛中的应用北京市清华附中高逸涵引言引入–众所周知，贪心算法是一个在信息学竞赛中应用广泛的高效算法。–但是有的时候，由于小规模针对性数据的存在，使得贪心算法不能得到正确的结果。–如何解决这一问题呢？部分贪心，顾名思义，就是在问题的局部采用贪心算法，而在其他部分采用其他算法。部分贪心引言为什么要“部分”贪心？–当问题的特殊情况普遍较小的时候，对于边界数据采用其他算法处理可以有效的回避特殊情况的讨论。–部分的普通算法对于总体时间复杂度影响并不大。–部分的贪心可以极大的提高算法的时间效率。引言举个例子：我们要最优化目标函数2()()()()5()2sin(5)4fxgxhxgxxhxx为了求得目标函数的最小值，我们可以首先贪心的求出趋势函数的最小值，然后在其左右寻找目标函数的最小值。()fx例题[例题1]骆驼[例题2]CowRelays[例题1]骆驼有p个人带着x个小包y个大包穿越沙漠每匹骆驼可以背的物体只能是下列四种组合之一：不超过3个小包；不超过2个大包；1个人与不超过2个小包；1个人和1个大包。问最少需要多少骆驼？数据范围：1=p,x,y=1000000000[例题1]骆驼首先，当所有人所带的包的种类确定以后，剩下需要的骆驼数目可以直接算出来。所以我们需要求的只是有多少个人带大包，多少个人带小包。很容易得到如下公式：(p,x,y分别为人,小包,大包数)但由于数据规模巨大，直接枚举显然行不通，需要另想办法。max(2,0)max(,0)min{,0}32xiypianspip[例题1]骆驼由于取整运算符的存在，导致直接数学计算变得比较困难。但是从整体趋势上来看，i的增加显然有利于ans的减小。那么按照贪心思想，我们需要尽量让人带着小包。max(2,0)max(,0)min{,0}32xiypianspip[例题1]骆驼我们很容易得到一个贪心算法：如果当前小包的个数=2并且还有人是空闲的，那么令这个人带着小包，否则令这个人带大包。很不幸，这个算法是错误的(x=3,y=3,p=1)。如何改进？[例题1]骆驼当人数和小包的数量都充分大的时候，令人带小包显然是没错的。经过验证，人数和小包数=20的时候，一定存在一个最优解使得存在一个骆驼带着人和小包。算法的正确性采用调整法很容易证明。而当人数和小包数有一个小于20时，可以采用枚举法解决问题。[例题1]骆驼已知朴素算法贪心算法解答大规模数据小规模特例部分贪心算法xx[例题2]CowRelays在一个无向图中有T条边，每个点至少和两条边相连，每条边有一个长度，询问从给定起点到给定终点的包含N条边的路最短是多长。数据规模：1=N=1000000000,1=T=100[例题2]CowRelays首先看到这一题目，我们的直观感受是，最优解一定是这样的一条路经：–首先从起点运动到某一个点上。–然后在这个点所连接的最小边上往复运动。–最后从这个点直接运动到终点。针对这一思想，我们很容易设计出一个贪心算法——枚举一条边做往复运动，然后从起点和终点分别向这条边走增量最短的路径到达。[例题2]CowRelays所谓增量最短路径，就是将所有边减去基准边之后得到的新图内的最短路径。ST5555477N=20基准边311113[例题2]CowRelays这样的贪心算法的复杂度为，但是运用部分贪心算法避免重复计算，可以将复杂度进一步降为算法瓶颈在于对于每条边，我们都要求一次最短路，我们希望在一次中解决所有最短路问题。3()OT2()OT[例题2]CowRelays回顾我们求最短增量路径的过程，显然，我们所求的最短增量路径一定是在边数确定时的最短路径。因此，我们只需要用动态规划预处理出源点到每一个点所走边数一定时所得的最短路径的长度，然后在贪心时枚举最短增量路径长度即可。SuvT2()OT2()OT2()OTSuvT3()OT()OT3()OTSuvT2()OT()ONT2()OT[例题2]CowRelays贪心算法：朴素动态规划：部分贪心：结果[例题1]骆驼时间复杂度效果贪心算法O(1)WrongAnswer朴素算法O(N)TimeLimitExceed部分贪心算法O(1)Accepted结果[例题2]CowRelays时间复杂度效果倍增算法较慢贪心算法较慢朴素算法很慢部分贪心算法很快3(log)OTN3()OT()ONT2()OT总结朴素算法——思路简单，算法低效，不易出错贪心算法——思路复杂，算法高效，易出错部分贪心——思路简单，算法高效，不易出错