算法合集之《一类算法复合的方法》.ppt

《算法合集之《一类算法复合的方法》.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一类算法复合的方法江苏省扬州中学张煜承问题描述维护集合S，初始时为空。有N个操作需要依次处理BX在S中插入一个整数XAY询问S中被Y除余数最小的数，如果有多个则任取一个1≤N≤40000，1≤X,Y≤R=500000允许离线算法初步分析算法1：对询问中每个不同的Y，维护它对应的询问当前的答案时间复杂度为O(N2)，不能解决问题但当询问中出现的不同Y的个数比较少时会很快，时间复杂度可以写成O(不同Y的个数×N)进一步分析当遇到一个询问"AY"时，要在S中寻找使得xmodY最小的数x把这里的x写成kY+r，其中0≤r

2、最小的数kY+r算法2：枚举k，找[kY,(k+1)Y)中的最小值。最后在这些最小值中取最优的一个例子S={2,3,6,8}Y=5012345678910…最小值为2最小值为62mod5=26mod5=1因此取6现在的问题：询问S中给定区间[a,b]内的最小数可以看成是询问≥a的最小数q(a)012345678910…aq(a)222366688+∞+∞…对很多连续的a，q(a)是相等的形成了若干个区间假设X所在的区间为[s,t]，现在在S中插入X[s,t]被拆分成了区间[s,X]和[X+1,t]ss+1…X-1XX+1…t-1taq(a)tttttttttss+1

3、…X-1XX+1…t-1tXXXXXtttt只有插入操作，所以一直在拆分区间，而不合并区间让时间倒流，把所有操作按照从后往前的顺序处理，那么区间就一直都在被合并了并查集把这里每个区间看作是一个集合，并维护它们对应的q每次操作近似地认为是均摊O(1)算法2对一个询问“AY”，需要询问O(R/Y)个区间，最多O(R)个区间一次询问的时间复杂度高达O(R)总时间复杂度O(NR)，也不能解决问题尝试着优化算法2的瓶颈在于一次询问需要处理的区间可能非常多，但只会发生在很少当Y非常小的时候一个例子：当Y>R0.5时，算法2已经可以接受了我们可以对这部分很少的Y的询问使用另一种算法

4、算法1当询问中的不同的Y很少时会很快，所以这里的另一种算法可以选择算法1算法3设一个边界值K对Y>K的询问使用算法2O(NR/K)对Y≤K的询问使用算法1O(NK)总时间复杂度O(NK+NR/K)将N和R看作常数，容易得出当K=R0.5时总时间复杂度最小，为O(NR0.5)算法3可以完全解决本题我们解决本题的重点是：不使用统一的算法，而是同时使用这个问题的两种算法，分别解决问题中的两个互补的部分我的论文里还有另一个例子SPOJRECTANGL这个问题同样可以通过同时使用两种不同的算法得到较好的解决总结一个问题往往可以被看作是由若干个相对并列的部分组成起来的通常对这些部

5、分使用统一的算法而有时这个问题可以使用多种算法解决，并且当这些算法应用在问题中不同特征的部分时，会有不同的效果这时就可以将这些算法复合，对问题的不同部分，根据它们的特征分别选择使用对这个部分较优的算法总结两个算法合并起来后，很神奇地得到了一个更优的算法这是因为这两种算法具有互补的优势，而我们把问题分成了若干部分，对每一部分根据其特征使用较优的算法，就使得两种算法的优势得到了结合总结每个算法都有各自的优势和劣势如果我们取长补短，充分利用它们的优势，也许就将会得出总体更优的算法这种取长补短的思想是非常重要的