浅谈二分策略的应用

二分策略在信息学竞赛中的应用华东师大二附中杨俊2019/9/9WinterCamp20052二分策略来源一个很简单的想法——在最坏情况下排除尽可能多的干扰，以尽可能快地求得目标效率高！对信息的充分利用，尽可能去除冗余，减少了不必要计算应用广！2019/9/9WinterCamp20053三种应用类型类型一：二分查找——应用于一般有序序列类型二：二分枚举——应用于退化了的有序序列类型三：二分搜索——应用于无序序列2019/9/9WinterCamp20054类型一：二分查找——应用于一般有序序列申明：“有序序列”，仅包含两层意思：第一，它是一个序列，一维的第二，该序列是有序的，即序列中的任意两个元素都是可以比较的，也就是拥有我们平时所说的全序关系2019/9/9WinterCamp20055类型一：二分查找——应用于一般有序序列二分查找的一般实现过程：（1）确定查找范围（2）选择基准元素（3）关键字比较，确定更精确的范围（4）判断结果，如不够精确，转至（2）2019/9/9WinterCamp20056例一：顺序统计问题[问题描述]给定一个由n个不同的数组成的集合S，求其中第i小的元素。例如：S={3,7,2,6,8,1,5}，i=4Answer=52019/9/9WinterCamp20057问题的一般解法二分查找的过程：（1）确定待查找元素在S中（2）在n个元素中随机取出一个记为x，将x作基准（3）设S中比元素x小的有p个（4）如果找出x，输出；否则转至（2）因为x是随机选出的，由简单的概率分析，可得算法的复杂度期望值为O(n)。如果ip，我们将范围确定为S中比x小的元素，求该范围内第i个元素；如果i=p，表示第i小的元素就是x如果ip，我们将范围确定为S中比x大的元素，求该范围内第i-p-1个元素；2019/9/9WinterCamp20058小结举这个例子，是想说明两点：第一，二分查找==logn第二，二分查找==平均??2019/9/9WinterCamp20059类型二：二分枚举——应用于退化了的有序序列与类型一中的二分查找相比，最大的区别在于这里的二分在判断选择哪一个部分递归调用时没有了比较运算*。显式有序序列隐含的退化了的有序序列2019/9/9WinterCamp200510例二：BTP职业网球赛[问题描述]N（N≤65536）—有N头奶牛（N是2P）参加网球淘汰赛。即N头奶牛分成N/2组，每组两头奶牛比赛，决出N/2位胜者；所有胜者继而分成N/4组比赛……直至剩下一头牛是冠军。K（1≤K≤N-1）—比赛既要讲求实力，又要考虑到运气。每头奶牛都有一个BTP排名，恰为1－N。如果两头奶牛的排名相差大于给定整数K，则排名靠前的奶牛总是赢排名靠后的奶牛；否则，双方都有可能获胜。Answer—现在观众们想知道，哪头奶牛是所有可能成为冠军的牛中排名最靠后的。并要求你列举出一个可能的比赛安排使该奶牛获胜。2019/9/9WinterCamp200511初步分析由于N很大，猜想可以通过贪心方法解决。K+11K+22……2KK3K+12K+1…………2019/9/9WinterCamp200512初步分析但我们很容易找到反例，例如：N=8,K=2但最优解为6。解决方法：枚举！31427586438748图BTP-167534821654264图BTP-22019/9/9WinterCamp200513性质：隐含的有序性如果排名为X的选手最终获胜，那么排名在X前的选手Y也可以获胜。证明：情况一：Y被Z≠X击败Z?…Y?…X?Z…?…?…?YXXXYYYX2019/9/9WinterCamp200514性质：隐含的有序性如果排名为X的选手最终获胜，那么排名在X前的选手Y也可以获胜。证明：情况二：Y被X击败Y?…X?………?…?XXYXYYYX2019/9/9WinterCamp200515问题的解决于是，我们可以二分枚举获胜的X。知道了X，能否很快构造出对战方式？可以证明这样贪心是正确的。如果利用静态排序二叉树，整个问题可以在O(Nlog2N)时间完成。例如N=8，K=2，X=667534821654264可以！2019/9/9WinterCamp200516小结算法的根本——在一个隐含的退化了的有序序列中进行二分查找00000000111111XAnsX≥Ans我们所寻找的——两种值的分界点。12019/9/9WinterCamp200517小结应用这类二分枚举的最优性问题近来很是热门（如NOI2003树的划分），而且这类试题很容易诱导选手直接采用动态规划或是贪心算法，而走入死胡同。所以，今后我们在考虑最优性问题时，应当注意问题是否隐含了一个有序的01序列，它是否可以用二分枚举将最优性问题转化为可行性问题。切记！“退一步海阔天空”。2019/9/9WinterCamp200518类型三：二分搜索——应用于无序序列二分策略有序序列无序序列2019/9/9WinterCamp200519例三：推销员的旅行[问题转述]这是一个交互式问题：在一个未知的竞赛图（即有N顶点，两点间恰只含一条边的有向图）中，通过不断询问任意两点之间边的方向，寻找一条哈密尔顿路。目标是询问次数尽可能少。思考...2019/9/9WinterCamp200520初步分析为了避免询问的盲目性，我们尝试使用增量法逐步扩展序列。我们先任意询问两个点不妨设询问结果是1到2有边，于是，我们就得到一条长度为1的线路。122019/9/9WinterCamp200521初步分析假设我们已设计了一条含有前i个点、长度为i-1的线路A1A2…Ai，我们希望再加入点i+1，将其变成长度为i的线路。A1A2A3Aii+1i+12019/9/9WinterCamp200522进一步分析这样的询问会不会问到底也没法插入i+1？不会！因为i+1有边到Ai。由此，我们得到了一种询问方法，但最坏情况下总的询问次数可能是O(N2)的。i+1i+1A1A2A3Ai2019/9/9WinterCamp200523二分搜索的使用由于对每个点Ak(1≤k≤i)，要么Aki+1，要么i+1Ak。且已知A1i+1，i+1Ai。因此，我们可以用二分搜索来寻找Ak，使i+1可以插入Ak与Ak+1之间。这样，我们所需要的询问次数仅为O(nlogn)。i+1i+1A1A[i/2]Aii+12019/9/9WinterCamp200524小结算法的根本——在一个无序的01序列中进行二分查找001011100111我们所寻找的——一个特殊的子串‘01’012019/9/9WinterCamp200525小结由此可见，这样的二分搜索方法往往应用于那些可行解较多，但需要高效地构造一组可行解的问题。i+1i+1A1A[i/2]Aii+1OP?2019/9/9WinterCamp200526总结在这里我仅简单地介绍了三个二分策略应用的例子，要涵盖二分策略的所有应用甚至是大部分应用都是困难的。这里我想指出的是：二分思想虽然简单，但是它的内容还是非常丰富的。我们不能让二分思想仅仅停留在一般有序数组上的最基本的二分查找，而应该扩展到更广泛的应用上。2019/9/9WinterCamp200527总结二分策略常与其它一些算法相结合，并借以隐蔽自己，逃离我们的视线。这就要求我们能有扎实的基本功丰富的解题经验大胆合理的猜测活跃的创造思维方可“以不变应万变”！2019/9/9WinterCamp200528