奥林匹克竞赛论文-浅谈信息学竞赛中的区间问题学习材料.doc

PAGE PAGE 4 浅谈信息学竞赛中的区间问题 华东师大二附中 周小博 【摘要】 本文对一些常用的区间问题模型做了简单介绍，包括一些算法及其正确性的证明，并从国际、国内的信息学竞赛与大学生程序设计竞赛中选了近10道相关例题，进行简要分析。 【关键字】 区间模型 转化 贪心 动态规划 优化 【引言】 在信息学竞赛中，有很多问题最终都能转化为区间问题：例如从若干个区间中选出一些满足一定条件的区间、将各个区间分配到一些资源中、或者将一些区间以某种顺序放置等。这类问题变化繁多，解法各异，需要用到贪心、动态规划等算法，并可以用一些数据结构优化算法。 本文将从几个方面对区间问题做一个简单的介绍，给出一些算法及其正确性的证明，具体分如下几个方面进行讨论： 1.最大区间调度问题 2.多个资源的调度问题 3.有最终期限的区间调度问题 4.最小区间覆盖问题 5.带权区间调度、覆盖问题 6.区间和点的有关问题 我们将对上述每个问题都给出基本模型、算法、证明及其实现，并从ACM-ICPC、CEOI、CTSC等比赛中选出了近10道相关例题，进行简要分析，有的例题还给出了各种不同的算法及其时间效率的分析。 本文中所讨论的问题主要由两个部分组成，一部分为近几年来各类竞赛题的归纳总结，另一部分来自于参考文献。 【正文】 1.最大区间调度问题 数轴上有个区间，选出最多的区间，使得这些区间不互相重叠。 算法： 将所有区间按右端点坐标从小到大排序，顺序处理每个区间。如果它与当前已选的所有区间都没有重叠，则选择该区间，否则不选。 证明： 显然，该算法最后选出的区间不互相重叠，下面证明所选出区间的数量是最多的。设为该算法所接受的第个区间的右端点坐标，为某最优解中的第个区间的右端点坐标。 命题1.1 当时，该算法所接受的第个区间的右端点坐标≤某最优解中的第个区间的右端点坐标。 该命题可以运用数学归纳法来证明。对于，命题显然为真，因为算法第一个选择的区间拥有最小右端点坐标。令，假定论断对为真，即。则最优解的第个可选区间所组成的集合包含于执行该算法时第个可选区间所组成的集合；而当算法选择第个区间时，选的是在可选区间中右端点坐标最小的一个，所以有。证毕。 设该算法选出了个区间，而最优解选出了个区间。 命题1.2 最优解选出的区间数量=该算法选出的区间数量。 假设，根据命题1.1，有。由于，必然存在某区间，在之后开始，故也在之后开始。而该算法一定不会在选了第个区间后停止，还会选择更多的区间，产生矛盾。所以,又因为是最优解选出区间个数，所以。 综上所述，算法选出的区间是最优解。 实现： 在判断某个区间与当前已选的所有区间是否重叠时,可以直接判断是否和所选的最后一个区间是否重叠。时间复杂度：排序+扫描=。 HYPERLINK 例题1：Latin America - South America 2001 Problem A 题目大意： 基因是由许多外显子（exon）组成，每个外显子都有一个起始位置和一个结束位置。两个外显子能够互相联接必须满足某个外显子的起始位置在另一个外显子的结束位置之后。给出个外显子，要求找到一条由外显子组成的基因链，使得外显子数量最多。 分析： 将每个外显子看作一个区间，两端点坐标分别为外显子的起始、结束位置。则现在的问题和原问题基本相同，只是端点上也不能重叠。这里就不写算法了。 2.多个资源的调度问题 有个区间和无限多的资源，每个资源上的区间之间不互相重叠。将每个区间都分配到某个资源中，使用到的资源数量最小。 定义区间集合深度为包含任意一点的区间数量的最大值，则显然有： 命题2.1 需要的资源数至少为。 设区间,,…,全部包含某一点，则必须把这些区间分配到不同资源中，故至少需要个资源。 其实竞赛中也出现过计算区间集合深度的题目，如 HYPERLINK North America – Northeast 2003 Problem E。下面给出计算区间集合深度的算法。 的计算方法： 将每个区间拆成两个事件点，按坐标从小到大排序，顺序处理每个区间。记录一个值，表示当前点被包含次数。每次遇到区间的左端点就+1，遇到右端点就-1。的值就是在该过程中的最大值。注意两个相同坐标不同类型的事件点的位置关系和区间是否能在端点处重叠有关，这在排序过程中应该注意。时间复杂度为排序+扫描= 由此可得出一个构造算法。 算法1： 计算出。将所有区间按左端点坐标从小到大排序，顺序处理每个区间。处理某个区间时，排除在它前面且与之重叠的区间所用到的资源，然后在1,2,3,…,这些资源中任意分配一个未被排除的资源。 证明： 设排序后的个区间分别为,,…, 命题2.2 每个区间都能分配到一个资源。 考虑任何一个区间，假设存在个区间在它前面且与之重叠。一定有，否则由于这个区