浅谈二分策略的应用

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