《国家集训队2008论文集 一类算法复合的方法》由会员分享，可在线阅读，更多相关《国家集训队2008论文集 一类算法复合的方法（15页珍藏版）》请在金锄头文库上搜索。
1、一类算法复合的方法江苏省扬州中学 张煜承问题描述维护集合S，初始时为空。有N个操作需要 依次处理 B X 在S中插入一个整数X A Y 询问S中被Y除余数最小的数，如果有 多个则任取一个 1N40000，1X,YR=500000 允许离线算法初步分析算法1：对询问中每个不同的Y，维护它对 应的询问当前的答案 时间复杂度为O(N2)，不能解决问题 但当询问中出现的不同Y的个数比较少时会 很快，时间复杂度可以写成O(不同Y的个数 N)进一步分析当遇到一个询问“A Y“时，要在S中寻找使 得x mod Y最小的数x 把这里的x写成kY+r，其中0rR0.5时，算法2已经可以接 受了 我们可以对这部分
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可以完全解决本题我们解决本题的重点是：不使用统一的算 法，而是同时使用这个问题的两种算法， 分别解决问题中的两个互补的部分我的论文里还有另一个例子 SPOJ RECTANGL 这个问题同样可以通过同时使用两种不同 的算法得到较好的解决总结一个问题往往可以被看作是由若干个相对 并列的部分组成起来的 通常对这些部分使用统一的算法 而有时这个问题可以使用多种算法解决， 并且当这些算法应用在问题中不同特征的 部分时，会有不同的效果 这时就可以将这些算法复合，对问题的不 同部分，根据它们的特征分别选择使用对 这个部分较优的算法总结两个算法合并起来后，很神奇地得到了一 个更优的算法 这是因为这两种算法具有互补的优势，而 我们把问题分成了若干部分，对每一部分 根据其特征使用较优的算法，就使得两种 算法的优势得到了结合总结每个算法都有各自的优势和劣势 如果我们取长补短，充分利用它们的优势 ，也许就将会得出总体更优的算法 这种取长补短的思想是非常重要的
