浅谈二分策略的应用
华东师大二附中 杨俊
【摘要】本文着重讨论三种不同类型的二分问题，意在加深大家对二分的认识。它们所考虑的对象从一般有序序列，到退化了的有序序列，最后到无序序列。事实上它们也正代表了二分策略的三种不同应用。
【关键字】二分、序、应用 【正文】
“二分”，相信这个词大家都再熟悉不过了。二分是一种筛选的法则，它源于一个很简单的想法——在最坏情况下排除尽可能多的干扰，以尽可能快地求得目标。
二分算法的高效，源于它对信息的充分利用，尽可能去除冗余，减少不必要的计算，以极大化算法效率。事实上许多二分问题都可以用判定树或其它一些定理来证明，它达到了问题复杂度的下界。
尽管二分思想本身很简单，但它的扩展性之强、应用面之广，或许仍是我们所未预见的。大家也看到，近年来各类竞赛试题中，二分思想的应用不乏令人眼前一亮的例子。下面是作者归纳的二分思想的三种不同类型的应用，希望能让读者有所收获。
类型一：二分查找——应用于一般有序序列
申明：这里所指的有序序列，并不局限于我们通常所指的，按从小到大或是从大到小排好序的序列。它仅包含两层意思：第一，它是一个序列，一维的；第二，该序列是有序的，即序列中的任意两个元素都是可以比较的。也就是拥有我们平时所说的全序关系。
虽说二分查找大家都再熟悉不过了，但这里还是先简要地回顾一下二分查找的一般实现过程：
（1） 确定待查找元素所在范围
（2） 选择一个在该范围内的某元素作为基准
（3） 将待查找元素的关键字与基准元素的关键字作比较，并确定待查找元素新的更
精确的范围
（4） 如果新确定的范围足够精确，输出结果；否则转至（2）
让我们看一个经典问题——顺序统计问题 [问题描述]
给定一个由n个不同的数组成的集合S，求其中第i小的元素。 [分析]
相信大家对这个问题都很熟悉，让我们回顾一下二分查找是如何应用于该问题上的。 （1） 确定待查找元素在S中
（2） 在n个元素中随机取出一个记为x，将x作基准 ．．
（3） 设S中比元素x小的有p个。
如果i 的元素，求该范围内第i个元素； 如果i>p，表示我们所要寻找的元素比x大，我们就将范围确定为S中比x大 的元素，求该范围内第i-p-1个元素； 如果i=p，表示第i小的元素就是x。 （4） 如果找出x，输出；否则转至（2） 因为x是随机选出的，由简单的概率分析，可得算法的复杂度期望值为O(n)。 [小结] 举这个例子，是想提醒大家两点： 第一，不要想当然认为二分查找就一定与logn有关。算法中的第（3）步，即我们通常所说的“分”并不要求每一次都必须在O(1)时间进行，“分”可以是建立在对序列的有效处理之上（比如上面这个例子中使用了类似于快速排序中的集合分割）。 第二，二分算法的“分”并不要求每次都必须平均（因为有时候可能很难做到这一点），只要不是每次都不平均就已经可以产生高效的算法了，这样也给使用随机化算法带来了契机。 近年来由于交互式试题的出现，也给予二分查找更多活力。相当多的二分查找问题都是以交互式试题的形式给出的。比如说，就上面这个例子，摇身一变就成了一道交互式的中等硬度问题（IOI2000）。两个题目如出一辙：你问第i小的，我问第(N+1)/2小的；解法当然也就依样画葫芦：你用随机取出的x，依照与x大小关系分成两段，我就随机取出x,y，依照与x,y大小关系分成三段；你的复杂度期望是O(n)，我的询问次数的期望也是O(N)。（具体细节这里不再展开，有兴趣的同学可以参考前辈的解题报告1） 类型二：二分枚举——应用于退化了的有序序列 二分策略并不总是应用于上述这样显式的有序序列中，它可能借助于问题某种潜在的关联性，用于一些隐含的退化了的有序序列中。与先前介绍的二分查找相比，最大的区别在于这里的二分在判断选择哪一个部分递归调用时没有比较运算。 我们还是先看一个问题——BTP职业网球赛（USACO contest dec02） [问题描述] 有N头奶牛（N是2K），都是网球高手，每头奶牛都有一个BTP排名（恰好为1—N）。下周将要进行一场淘汰赛，N头奶牛分成N/2组，每组两头奶牛比赛，决出N/2位胜者；N/2位胜者继而分成N/4组比赛……直至剩下一头牛是冠军。 比赛既要讲求实力，又要考虑到运气。如果两头奶牛的BTP排名相差大于给定整数K，则排名靠前的奶牛总是赢排名靠后的；否则，双方都有可能获胜。现在观众们想知道，哪头奶牛是所有可能成为冠军的牛中排名最后的，并要求你列举出一个可能的比赛安排使该奶牛获胜。（限制N≤65536） [分析] 由于N很大，我们猜想可以通过贪心方法解决。 我们希望排名靠前的选手总是“爆冷”输给排名靠后的选手。于是我们让1输给K+1、 1 2000-2002集训队论文《中等硬度解题报告》高岳 2输给K+2??每一轮中每一局总是选择未比赛的排名最前的选手，输给一个排名最靠后的选手（如果有的话）。 但我们很容易找到反例，例如：N=8, K=2，由上述贪心方法我们得到对阵方式结果为4，见图BTP-1（其中X?Y表示X战胜Y）。 3?1 4?2 7?5 8?6 4?3 8?7 4?8 6?7 5?3 4?8 2?1 6?5 4?2 6?4 图BTP-1 图BTP-2 但最优解为6，见图BTP-2。究其原因，因为我们不知道最优解是多少，所以我们是在盲目地贪心。事实上，最优解的6在第一轮就被我们淘汰了，当然就得不到最优解喽！ 要想知道最优解？枚举！同时考虑到一个很显然的结论——如果排名为X的选手最终获胜，那么排名在X前的选手也可以获胜。 显然归显然，证明它我们还需要动一点小脑筋。假设排名X的选手最终获胜，我们通过对该对战方式的局部修改，构造出一种新的对战方式使任意排名Y 因此，我们就可以用二分枚举最终获胜的X，大大提高了算法效率。 现在的问题是，如果我们知道最终获胜的是X，我们能否很快构造出一种对战方式或是证明不存在吗？可以，我们仍旧使用贪心，不过因为我们知道最终谁获胜，所以我们采用倒推。 每一轮，我们都让已有选手去战胜一个排名最靠前的还未出现的选手，由该方法产生的对战方式就如图BTP-2所描述那样。至于最靠前的未出现选手如何找，我们可以采用静态排序二叉树实现，这里不再展开，读者可以自己考虑。 可以证明这样贪心是正确的（证明方法同前面的证明类似，这里也不再重复）。整个问题可以在O(Nlog2N)时间完成。 [小结] 对于这类需要二分枚举的问题，其实算法的根本是在一个隐含的退化了的有序序列中进行二分查找，只是这个序列仅含有0和1两种值。上例中当X 让我们再看一个问题——奖章分发（ACM/ICPC CERC 2004） [问题描述] 有一个环形的围墙，围墙上有一些塔，每个塔中有一个守卫。现在要发给每个守卫一些奖章，第i个守卫需要P[i]个奖章。每个守卫自己的奖章必须都是不同种类的，而且相邻的两个守卫得到的奖章也不能有任何一个相同。问至少应准备多少种不同的奖章。（限制：2≤n≤10000，1≤P[i]≤100000） [分析] 假如围墙不是环形的，我们很容易用贪心算法解决：每次发给守卫尽可能多的已准备的奖章，如果不够就再新准备若干种以满足需要。但现在围墙是环形的，最后一个守卫与第一个守卫也不能有重复的奖章，这就是问题的难点。 于是我们尝试将这一难点引入状态，用动态规划求解（动态规划是求解最优性问题的一种常用方法）。 令a[i,j]表示前i个守卫已安排妥当，且第i个守卫有j个奖章与第一个守卫相同，则除第一个守卫已有的P[1]种奖章外，至少还需要的奖章种数。 第i-1个守卫 k P[i-1]-k 第i个守卫 j P[i]-j 与第一个守卫相同的奖章数目 与第一个守卫不同的奖章数目 如图，假设第i-1个守卫有k个奖章与第一个守卫相同，由于这k个奖章与第i个守卫的j个奖章必须互不相同，易知j+k≤P[1]；又由于第i-1个守卫的另外P[i-1]-k个奖章必须与第i个守卫的另外P[i]-j个奖章不同，设需要增加X种奖章，则 a[i-1,k]+X ≥ (P[i]-j)+(P[i-1]-k) 得到X ≥ (P[i]-j)+(P[i-1]-k) - a[i-1,k] 于是我们有 a[i,j]??0?k?P[i?1],k?P[1]?j0?k?P[i?1],k?P[1]?jmin{a[i?1,k]?max{0,(P[i]?j)?(P[i?1]?k)?a[i?1,k]}}min{max{a[i?1,k],P[i]?P[i?1]?j?k}} 显然就这样做复杂度高达O(n*Pmax2)。即使使用了优化，也很难得到令人满意的结果， 我们只得另辟蹊径。 考虑到如果有P[1]+X种奖章，存在一种分发方案满足要求，那么如果我们有P[1]+X+1种奖章，也一定存在可行方案（大不了其中一种我们不用）。这个性质非常重要，因为由此，我们可以就用二分枚举X，再逐个判断是否有可行方案的方法求得结果。 所以原先问题就转化为——如果我们已经知道共有P[1]+X种奖章，我们能否很快判断是否存在满足要求的分发方案呢？答案是肯定的。 方法仍旧是动态规划2，状态表示也类似，a[i,j]表示共有P[1]+X种奖章，前i个守卫已安排妥当，且第i个守卫有j个奖章与第一个守卫相同是否可能。 则状态转移变为： a[i,j]?or(a[i?1,k]) 0?k?P[i?1],k?j?P[1],P[i?1]?k?P[i]?j?X表面上看状态转移仍旧很繁琐，k的取值有很多限制。但我们仔细观察，第二、三条合起来是P[i-1]+P[i]-X-j ≤ k ≤ P[1]-j。 对于确定的i，k的取值范围在数轴上的表示是一条长度确定的线段，且线段的位置由j确定。原先第一条限制只不过是再给线段限定一个范围，去除多余无意义的部分（如图）。 2 准确地说应该是递推
相关推荐：
loading