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