漫话二分(上)

    二分思想真的是无所不在,即使在中文系的专业课中我们也能见到这个词。在语言学概论中我们提到,一个音位可以由一组区别特征确定下来,这些区别特征总是以只具有“是/否”、“有/无”等两种对立属性的“二元偶分组”形式存在,因为这样可以最方便最快捷地确定出一个元素。这有点像猜数字一样,我想一个数字后让你来猜,我告诉你你的猜测是大了还是小了。只是在这里,回馈的信息不再是大小,而是“辅音/元音”、“口音/鼻音”、“浊音/清音”、“送气/不送气”等形式逐层细分。这让人联想到5张卡片猜年龄的老把戏,一系列火星的称球问题,基于比较的排序算法的复杂度下界,或者经典的20q在线游戏
    一个有趣的事实是,相当多的人都错误地理解了“二分”这个词,但他们在生活中却拥有很强的二分意识。我们语言学概论的老师(这里就不说是谁了)在讲解二分时举了一个甚为荒谬的例子:如果你要在房间里找一根针,那么你可以把房间划分为两半,如果这一半找不到的话说明针一定在房间另一半,此时再把那一半分成两部分,不断分分分分分最后总能找到针的位置。这是这位老师无数荒唐的例子中的冰山一角,因为这个“二分”与搜索别无二致。这个“二分”的判断环节并不是即刻返回的,而且最关键的是它并不具有规模减半的功能,或者说一旦返回“真”后我们并不会再接着二分下去。如果让我来举例子的话,同样是拿找东西打比方,在合唱队中找出跑调了的人是一个绝佳的例子,因为在合唱中我们能轻易分辨出一个不和谐的声音(虽然无法准确判断这个声音是从哪儿传来的),不断叫当前的人的其中一半来合唱便可渐渐判断出那个人的位置。但讽刺的是,这老师在举这个错误例子的同时,竟然在不自觉地用二分法来调整课件的字号。他发现这一页ppt的字号太小了,我们可能看不清,于是希望让字号尽可能的大但又不致于大到显示不下。他开始尝试40号,发现字已经超出屏幕了;然后把字体改成20号,又觉得还能再大一些;进而又改到28号(工具栏上的字号调整以4为步长),最后确定到了24号字。

    如果真的叫一个课讲的好的老师来说二分,课程可以变得相当有意思。每次回我们高中时我都讲了很多次课,我最喜欢聊到的话题之一就是二分。从猜数游戏引入二分查询有序队列中的指定元素,然后提出一些标准的有序队列二分搜索的实际应用,比如解方程x^x=100一类的问题。紧接着提出二分的各种有趣的变形,例如如何在有序整数序列中查询A_i=i的元素。提出这些问题的目的就在于告诉大家,二分的思想不仅仅是用在猜数游戏一类的情况下。二分判断并不只限于“比目标值大/比目标值小”,只要能判断出目标值在哪边都行,例如在这里,A_i<i表明目标元素一定还在右边,A_i>i则表明目标元素在左边。

 i  =    1   2   3   4   5   6   7   8   9   10
A_i = -100 -20  -3   0   2   6  13  14  27  298


    另一个经典的变形则是分段有序队列中的二分查询。假如有这么一个数列,它可以分为前后两个部分,两段各是一个递增数列,并且后一段的最大值比前一段的最小值还要小。比如说,数列12, 15, 19, 3, 6, 7, 9, 10就是这样一个数列。这相当于是一个有序数列循环移动之后的结果。如何在这个数列中查询指定的元素呢?事实上,这种“有序序列”虽然经过了变形,但丝毫不影响二分法的应用,因为我们依旧能判断出目标值在当前值的哪一边(这是很显然的,我不多解释了),这就已经足够了。
    不结合实际应用的话,这些似乎没有实用价值的理论会变得乏味。其实,只要仔细思考,生活中对应的现象总是有的。我的秘方就是,想不出例子就想MM,爱情的复杂性保证其蕴含了各种千奇百怪的数学模型。一想到爱情,分段有序队列就能用上了。不妨为恋爱前后的“愉悦程度”建一个简单的模型:在恋爱之前,你会为找不到MM而越来越难过;一旦开始热恋愉悦值瞬间达到极大;之后热情会慢慢减小,但愉悦值始终比恋爱前要大。好啦,如果你想出一道题的话,问题背景已经是现成的了,不妨再定义一个符合这个模型的且不能直接解出来的分段函数,编几句形如“科学家发现恋爱前的愉悦值以a减某某某的速度递减,恋爱后则变为曲线a加某某某”的话,然后就来看看有多少人还能想到二分法吧。一般说来,好的题目背景起到了一个很强的干扰作用:题目背景越顺理成章,问题描述越是简单,看清问题背后隐藏的算法障碍就越大。另外,如果你给的函数巧妙到还需要大家先证明它的单调及有界,那这题目就真的绝了。

    要比谁的题目更绝,那绝对比不过USACO。USACO月赛中的二分题是真牛B了。我对二分的热情是相当的高。为高一高二的几个人备战省选时,我出了好几套模拟题,前面四套题每套都有一道来自USACO月赛的二分题。这个二分题是越来越诡异,以至于大家越来越难看出这套题里面哪道要用二分了。
    第一套题里的二分题是一个简单题:把一个长为N的数列划分为M段,要求每段数之和的最大值最小。例如,把100 400 300 100 500 101 400分割成5块,则100 400 | 300 100 | 500 | 101 | 400是最优方案之一,最大值500已经不能再小了,这个题一看就知道是二分后贪心判断,“最大值最小”之类的关键词几乎成了二分题的信号灯。像什么最小权值最大的完全匹配、瓶颈生成树问题(求最大边最小的生成树:二分后判断连通)、寻找权值波动最小的路径(找一条从A到B的路径使得所经过的边的最大权值和最小权值相差最小:枚举下界二分上界判断连通,滑动窗口更好),都是二分的经典问题。
    第二套题中的二分也是“最大值最小”类的问题,只是要更复杂一些:在带权无向图中,选择一些边使得A、B两点连通,要求费用最小。费用是这样算的:先从图中选出K条边(K值是给定的),免费;然后从图中选择其它你需要的边,费用为这些边的最大权值。这个题里,选边过程的先后顺序有一个很强的误导作用。事实上,正确的算法应该是先二分这个最大权值,再来判断把K条免费边的机会用上能不能把A、B连通,换句话说就是要想把A、B连通还差的边数超没超过K。当时做这个题时,不少人二分法是想到了,但却怎么也想不到该如何计算最少还需要多少条边才能连通A、B两点。其实方法很简单,把不超过当前二分出来的那个“最大权值”的所有边权值设为0,其它边的权值设为1,然后找一下最短路就可以了。
    第三次的二分题就不容易看出来了。给定一个有向图,每条边都有两种权值,时间和愉悦值。叫你寻找一条回路(不经过重复的边),使得愉悦值之和与时间总和之比最大。能想到这个题目是二分的话,那就真的很厉害了。二分最优比率C,然后给每条边设置一个新的权值,它等于C倍的时间减去愉悦值,再来判断是否有负权回路。这是怎么来的呢?不妨这样来看:对于任意一条回路,所求比率等于(Σ愉悦值)/(Σ时间)。如果二分出来的最优比率C偏小了,那说明满足(Σ愉悦值)/(Σ时间)>C的回路多得是,移动一下便有C*(Σ时间)-(Σ愉悦值)<0,即在新的权值设定下存在负权回路。如果没有负权回路的话,说明所有回路的比率都比C小,这就说明我们的C取大了。同样的思路也可以用来解决最优比率生成树问题。     第四次的二分题可就是真的牛B大发了。假设有一个长度为N的数组A_i,里面的每个数都不一样。但是呢,你不知道数组里的数是多少。给出若干个形如“从A_i到A_j中的最小值是x”的命题,问你第一个和前面有矛盾的命题在哪里。例如,给你四个命题:A_1到A_10的最小值是7,A_5到A_19的最小值是8,A_3到A_12的最小值是5,A_11到A_15的最小值是4。第三句话显然是错的,否则前两个区间中至少有一个的最小值也达到了5。     这个题难就难在,我们需要挖掘出“矛盾”的本质。究竟每一条命题给我们带来了什么信息呢?假设我告诉你,A_1到A_10的最小值是7,你仍旧不能推断出任何一个数,但有两点是肯定的:第一,这10个数里有一个数字7;第二,这里面的每个数都不能小于7。假设我们再给出一个A_5到A_19的最小值是8呢?此时,我们得知A_5到A_19里面有一个8,并且A_5到A_19的所有数都不小于8。注意!此时从A_5到A_10这一段中的数字下界升级了!由此得到启发,这些条件给出的信息说穿了就是每个位置可能出现的数的下界,它就是覆盖它的那些区间中的最大值。我们可以把区间端点排序,从左到右扫描一遍,用堆不断更新当前的最大值。在确定完每个位置可能的最小数后,我们开始寻找一个满足这些条件的解。由于数组中没有相同的数,因此对于所有回答“最小值为x”的区间,x必需出现在它们的交集中。如果这个交集为空,或者交集里面所有的位置(因下界过大)都不能取这个数,那么我们就可以肯定地说这一组条件是有矛盾的。如果我们顺利地给每个区间都安排好最小值所在位置,这立即说明了该组条件没有矛盾,因为我把其它那些没确定下来的位置取到无穷大,满足全部条件的数组就构造出来了。于是,我们有了一个O(nlogn)判断一组命题是否有矛盾的算法。     这个题有趣就有趣在,上述算法虽然高效,但却只能判断命题组是否矛盾,不能检测矛盾首次出现的位置;而在线判断命题是否矛盾(一个命题一个命题地往里面加)反而要慢些。于是呢,二分答案就派上用场了:二分前面的无冲突命题的最大长度,然后用上面的O(nlogn)算法来判断看是不是有矛盾。     然而,上面这些二分题都还太“正统”了一些。拼完了NOI之后,我便在网上自由潇洒地学习各种自己感兴趣的算法,看到了不少真正另类而绝妙的二分……

20 条评论

回复给 sqybi 取消回复

55  +    =  59