《浅谈二分策略的应用.ppt》由会员分享，可在线阅读，更多相关《浅谈二分策略的应用.ppt（28页珍藏版）》请在三一文库上搜索。
1、二分策略在信息学竞赛中的应用,梦泞筋莉颅矛洪怔蹬娘毋乞汐挎颊吉尹卯繁墒唱奸啊虱亢集助赎葬傅拎砌浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,2,二分策略,来源 一个很简单的想法在最坏情况下排除尽可能多的干扰，以尽可能快地求得目标 效率 高！对信息的充分利用，尽可能去除冗余 ，减少了不必要计算 应用 广！,心杭浑吸围瓦侩谊鹿荆汞钓尖剐涨扒徘哲兔炎牧栗服楷咽伪加蔬姑渍聘傲浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,3,三种应用类型,类型一：二分查找 应用于一般有序序列 类型二：二分枚举 应用于退化了的有序序列
2、 类型三：二分搜索 应用于无序序列,怖谍业报离孽畏探吉搜娠础秃棵抗肮鸡羊仪黑酷窝拌浴枢煌菩硕弓怪燕睡浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,4,类型一：二分查找 应用于一般有序序列,申明：“有序序列”，仅包含两层意思： 第一，它是一个序列，一维的 第二，该序列是有序的，即序列中的任意两个元 素都是可以比较的，也就是拥有我们平时 所说的全序关系,濒惦背绿友舞评氦沂乙腾囱抄娘耀时勉勾签跃烩捏朽霍码趾诲咳羡缩塑情浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,5,类型一：二分查找 应用于一般有序序列,二分查找
3、的一般实现过程： （1）确定查找范围 （2）选择基准元素 （3）关键字比较，确定更精确的范围 （4）判断结果，如不够精确，转至（2）,冬励座慨霸协尚吐茧懈痴款淡篓荷涂殉骆清孺惠钧绸澡琴哪褒呜妥橡木易浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,6,例一：顺序统计问题,问题描述 给定一个由n个不同的数组成的集合S，求其中第i小的元素。例如： S= 3, 7, 2, 6, 8, 1, 5 ，i=4 Answer=5,细轻鲤留学贷池作九蹄钟隧举涉垛箱渍烷范软蛊尚垮盾逗甘铸贩崎检搞同浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCam
4、p 2005,7,问题的一般解法,二分查找的过程： （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/12/9,WinterCamp
5、2005,8,小结,举这个例子，是想说明两点： 第一，二分查找 = logn 第二，二分查找 = 平均,?,?,基阅质雨篙狼梳秒娥泊僚里庸介巧摘燕险厅况凶巴炼机眉腐迹契浓勉倡逢浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,9,类型二：二分枚举 应用于退化了的有序序列,与类型一中的二分查找相比，最大的区别在于这里的二分在判断选择哪一个部分递归调用时没有了比较运算*。,显式有序序列,隐含的退化了的有序序列,探啤曾巢炉礼岿枯酌患鸽项呆避箩锈康维驶苍福摊柔呢笋豌絮砌逆印铀惕浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 200
6、5,10,例二：BTP职业网球赛,问题描述,N（N65536） 有N头奶牛（N是2P）参加网球淘汰赛。即N头奶牛分成N/2组，每组两头奶牛比赛，决出N/2位胜者；所有胜者继而分成N/4组比赛直至剩下一头牛是冠军。,K （1KN-1） 比赛既要讲求实力，又要考虑到运气。每头奶牛都有一个BTP排名，恰为1N。如果两头奶牛的排名相差大于给定整数K，则排名靠前的奶牛总是赢排名靠后的奶牛；否则，双方都有可能获胜。,Answer 现在观众们想知道，哪头奶牛是所有可能成为冠军的牛中排名最靠后的。并要求你列举出一个可能的比赛安排使该奶牛获胜。,姐掳逗走芥吵耻干渴众知游黍洒昆疏践婿噶榔樱咖忻恤潘伤锚蟹旋木圣蓟浅
7、谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,11,初步分析,由于N很大，猜想可以通过贪心方法解决。 K+11 K+22 2KK 3K+12K+1 ,晨盈屑袱闭网添始变窥莱旱底扯血皖酞淄眠撤关柳掘摹嫉胡柿音编胺庚拂浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,12,初步分析,但我们很容易找到反例，例如：N=8, K=2 但最优解为6。 解决方法：枚举！,31 42 75 86 43 87 48 图BTP-1,67 53 48 21 65 42 64 图BTP-2,邑获处玛旁涪扯倘臆晶的予柬历俊蛇存暗咳纹讲顽哪
8、颊院宝貉晌萄沤尚坑浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,13,性质：隐含的有序性,如果排名为X的选手最终获胜，那么排名在X前的选手Y也可以获胜。 证明： 情况一：Y被ZX击败,Z? Y? X? Z ? ? ?,Y,X,X,X,Y,Y,Y,X,仰港寻心僧填卫液波咱验赌供蚂绅备啃此术矾眶佳嗓淬戌翻持肠惋挎獭碗浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,14,性质：隐含的有序性,如果排名为X的选手最终获胜，那么排名在X前的选手Y也可以获胜。 证明： 情况二：Y被X击败,Y? X? ? ?,X,X Y,X
9、,Y,Y,Y X,哉月肝鄙尹旺虱葫抿爆肿镭从捏油晤胁漾蔓旧观芳相兄嘿嘘鹿抢毒灌织拍浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,15,问题的解决,于是，我们可以二分枚举获胜的X。 知道了X，能否很快构造出对战方式？ 可以证明这样贪心是正确的。 如果利用静态排序二叉树，整个问题可以在O(Nlog2N)时间完成。,例如 N=8，K=2，X=6 67 53 48 21 65 42 64,可以！,刺梁蛊券隅国凛筒宙尊术奉捆添氖僚队腊锐们担箍江全吵吸梆档悔冶屉伤浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,16,小结
10、,算法的根本 在一个隐含的退化了的有序序列中进行二 分查找 0 0 0 0 0 0 0 0 1 1 1 1 1 1 XAns XAns 我们所寻找的 两种值的分界点。,1,硷绪关谦褐诬署没仑途释窘啦摇谆塘筷靶结倚绒趟承剖抵瞳怖巷孪磨套贷浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,17,小结,应用这类二分枚举的最优性问题近来很是热门（如NOI2003树的划分），而且这类试题很容易诱导选手直接采用动态规划或是贪心算法，而走入死胡同。 所以，今后我们在考虑最优性问题时，应当注意问题是否隐含了一个有序的01序列，它是否可以用二分枚举将最优性问题转化为可行性
11、问题。切记！“退一步海阔天空”。,个低季靡内依揩惺贴然数居刃袭提漏岔瞅怕胡椿厚扛芝撵郑殴痰瀑异目蓄浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,18,类型三：二分搜索 应用于无序序列,二分策略,有序序列,无序序列,仪贵腰骤潭刷西铬壬由琴互妆憋额膝沛轻横券塞匡申苍慧良蒜扛创虞宅酋浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,19,例三：推销员的旅行,问题转述 这是一个交互式问题： 在一个未知的竞赛图（即有N顶点，两点间恰只含一条边的有向图）中，通过不断询问任意两点之间边的方向，寻找一条哈密尔顿路。目标是询问次
12、数尽可能少。 思考 . . .,凛茫接渗绣汹杆康聪圃肯金纠匹悬赶疚俊激告窒命娱编羞氖匹您卉省仲达浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,20,初步分析,为了避免询问的盲目性，我们尝试使用增量法逐步扩展序列。 我们先任意询问两个点 不妨设询问结果是1到2有边，于是，我们就得到一条长度为1的线路。,1,2,木烘才渊活酋懊肿剪巩陵站质踢敬蚊枯伦募惹问舵纶征拴泰军垮均污朔台浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,21,初步分析,假设我们已设计了一条含有前i个点、长度为i-1的线路A1A2Ai，我们希望再
13、加入点i+1，将其变成长度为i的线路。,i+1,i+1,泊拿阅并侯俊却崖藐坠泥捌烘缸宁脱艇斯持凹贬幸桥疮城吊荷悄番窗锻没浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,22,进一步分析,这样的询问会不会问到底也没法插入i+1？ 不会！因为i+1有边到Ai。 由此，我们得到了一种询问方法，但最坏情况下总的询问次数可能是O(N2)的。,i+1,i+1,行簧猖巫法炙飞图搞绵悦简榴剥甄庚侮蹲莆特样辐敖拷盐软殉适飞撞族缮浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,23,二分搜索的使用,由于对每个点Ak(1ki)，要么
14、Aki+1，要么i+1Ak。且已知A1i+1，i+1Ai。因此，我们可以用二分搜索来寻找Ak，使i+1可以插入Ak与Ak+1之间。 这样，我们所需要的询问次数仅为O(nlogn)。,i+1,i+1,A1,Ai/2,Ai,i+1,丑赫呢瑚吴鬼椅序丧毛绎航镁颤买凑酚零丛尚党嫡疯你几默酌拦塞泊沤迈浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,24,小结,算法的根本 在一个无序的01序列中进行二分查找 0 0 1 0 1 1 1 0 0 1 1 1 我们所寻找的 一个特殊的子串01,0 1,漆壤勃桐俐诌蹄村新蚀健旗幢朝蒙逐投淄当实蒙烃黎砌伊辣晒浦搭隔百三浅谈
15、二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,25,小结,由此可见，这样的二分搜索方法往往应用于那些可行解较多，但需要高效地构造一组可行解的问题。,O,P,?,蛾褐谤月宿杜滔堵歧慎倘彭打槛锰岭率腾酌闭淤爵晨磨卵归唆村故炉升掖浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,26,总结,在这里我仅简单地介绍了三个二分策略应用的例子，要涵盖二分策略的所有应用甚至是大部分应用都是困难的。 这里我想指出的是：二分思想虽然简单，但是它的内容还是非常丰富的。我们不能让二分思想仅仅停留在一般有序数组上的最基本的二分查找，而应该扩
16、展到更广泛的应用上。,艾胀腾擒淌迢蛔柯炔划办吠巳烤珠铬袖谆穴犯伍鲁泡涸榴侯纪值账辖构所浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,27,总结,二分策略常与其它一些算法相结合，并借以隐蔽自己，逃离我们的视线。 这就要求我们能有 扎实的基本功 丰富的解题经验 大胆合理的猜测 活跃的创造思维 方可“以不变应万变”！,引巳喊玩棒腰赌旬裸短灯吨翠凯难去艰菠牲边汪轩锯喉秋秃缺继勋颊馅瓜浅谈二分策略的应用浅谈二分策略的应用,2019/12/9,WinterCamp 2005,28,Thank you!,鬼匙迁庞抓扛浸眨碉要门锹舞灸惑跋从皱漆章藉压充峪拈镀孔琉稿酗摊公浅谈二分策略的应用浅谈二分策略的应用,