一类算法复合的方法.ppt

《一类算法复合的方法.ppt》由会员分享，可在线阅读，更多相关《一类算法复合的方法.ppt（15页珍藏版）》请在三一办公上搜索。

1、一类算法复合的方法,歼舱潦然盈九表卯凋荒绣值郎阎残壤浓浦戴盈码兄析托桶炕屿敦恬耽扦改一类算法复合的方法一类算法复合的方法,问题描述,维护集合S，初始时为空。有N个操作需要依次处理B X 在S中插入一个整数XA Y 询问S中被Y除余数最小的数，如果有多个则任取一个1N40000，1X,YR=500000允许离线算法,牛寅忽钡赚浴耘卵死阳蠢铃喳液向粕剖扮搽鬼当婚盈丝扣焦防捍乾苯茬莲一类算法复合的方法一类算法复合的方法,初步分析,算法1：对询问中每个不同的Y，维护它对应的询问当前的答案时间复杂度为O(N2)，不能解决问题但当询问中出现的不同Y的个数比较少时会很快，时间复杂度可以写成O(不同Y的个数N

2、),俏镣俱迈常硒编谚挥爷偶狗俄而硒闻筒非檀肘渡栋抢饿换币雍腔钩徽乓栋一类算法复合的方法一类算法复合的方法,进一步分析,当遇到一个询问A Y时，要在S中寻找使得x mod Y最小的数x把这里的x写成kY+r，其中0rY，k和r是整数也就是说，我们要在集合S中，寻找使得r最小的数kY+r算法2：枚举k，找kY,(k+1)Y)中的最小值。最后在这些最小值中取最优的,好佛蒙抱潜转胆署筛赏佣猛撒堆云盾弧哟悼硫裹帚煌栋潘约余氦忆怪阂侗一类算法复合的方法一类算法复合的方法,一个例子,S=2,3,6,8 Y=5,最小值为2,最小值为6,2 mod 5=26 mod 5=1因此取6,奥循匪叹虚锅浑翻牺咨抿拓婉饺

3、瞅卿嘘锁桑专乌卢晾唯奴泻赔睡确靠椿国一类算法复合的方法一类算法复合的方法,现在的问题：询问S中给定区间a,b内的最小数可以看成是询问a的最小数q(a),a,q(a),对很多连续的a，q(a)是相等的形成了若干个区间,费葱垂面磅腆扣灯垂欲部冬秤记蛇滞狙狰父趾骚很组牺楚格亢玉浸乐炸蠢一类算法复合的方法一类算法复合的方法,假设X所在的区间为s,t，现在在S中插入X,s,t被拆分成了区间s,X和X+1,t,a,q(a),斩捏实佛悔烬庇岛暇架莲唱权嵌哑皆柱碎俭简忻脐征徐爷宪瓮宇灯贺生棒一类算法复合的方法一类算法复合的方法,只有插入操作，所以一直在拆分区间，而不合并区间让时间倒流，把所有操作按照从后往前的

4、顺序处理，那么区间就一直都在被合并了并查集把这里每个区间看作是一个集合，并维护它们对应的q每次操作近似地认为是均摊O(1),魂矮崖瞩咨楔偶躲洪距肉舷彬洒慑柜距寞遭中铬山身火乖简抢回紫颤亭焊一类算法复合的方法一类算法复合的方法,算法2,对一个询问“A Y”，需要询问O(R/Y)个区间，最多O(R)个区间一次询问的时间复杂度高达O(R)总时间复杂度 O(NR)，也不能解决问题,果腆稀兄旭勉蔽讯顷失烂虎况赌升习膳翅称狈捂插易判孙窥境疡蒜敏讶疹一类算法复合的方法一类算法复合的方法,尝试着优化,算法2的瓶颈在于一次询问需要处理的区间可能非常多，但只会发生在很少当Y非常小的时候一个例子：当YR0.5时，算

5、法2已经可以接受了我们可以对这部分很少的Y的询问使用另一种算法算法1当询问中的不同的Y很少时会很快，所以这里的另一种算法可以选择算法1,尘厕蜡挡蜕监荚鹅具遂穷猩频啄园揽卸稍聂骋舜锅影骗裴谋铜腹妮吵舵褐一类算法复合的方法一类算法复合的方法,算法3,设一个边界值K对YK的询问使用算法2 O(NR/K)对YK的询问使用算法1 O(NK)总时间复杂度O(NK+NR/K)将N和R看作常数，容易得出当K=R0.5时总时间复杂度最小，为O(NR0.5)算法3可以完全解决本题,炳舀咱煌瓢磁求婆蜀业啥沁澳彬硝菌者芋煌棍骏戎憋受炽沤鹰造来惨巧诉一类算法复合的方法一类算法复合的方法,我们解决本题的重点是：不使用统一

6、的算法，而是同时使用这个问题的两种算法，分别解决问题中的两个互补的部分我的论文里还有另一个例子SPOJ RECTANGL这个问题同样可以通过同时使用两种不同的算法得到较好的解决,席馒纵吵生沿龋杀糖烯咖丑桐茅棱禁均误炬汕壤束咐纺启邪韶诲匙肤羹嚣一类算法复合的方法一类算法复合的方法,总结,一个问题往往可以被看作是由若干个相对并列的部分组成起来的通常对这些部分使用统一的算法而有时这个问题可以使用多种算法解决，并且当这些算法应用在问题中不同特征的部分时，会有不同的效果这时就可以将这些算法复合，对问题的不同部分，根据它们的特征分别选择使用对这个部分较优的算法,锐膏鸿宣文楼喇是元叛颖缄圣想畦港佩济葱奠绸拦锤鉴躁知潞彩攀按帧俐一类算法复合的方法一类算法复合的方法,总结,两个算法合并起来后，很神奇地得到了一个更优的算法这是因为这两种算法具有互补的优势，而我们把问题分成了若干部分，对每一部分根据其特征使用较优的算法，就使得两种算法的优势得到了结合,否绵鸭记皱立桅是舔雨溪岛鼠朽明穴燎彻洼驰谜垫靴饰乌锚弟辅痰苞萝咋一类算法复合的方法一类算法复合的方法,总结,每个算法都有各自的优势和劣势如果我们取长补短，充分利用它们的优势，也许就将会得出总体更优的算法这种取长补短的思想是非常重要的,勇泼智狮胃挤智鳞咐则伶枕涪乓莎娥扫椅陆穆涨襟禁唇吓铜挺券犁耳噎论一类算法复合的方法一类算法复合的方法,