国家集训队2008论文集浅谈信息学竞赛中的区

浅谈信息学竞赛中的区间问题华东师大二附中周小博引言在信息学竞赛中，有很多问题最终都能转化为区间问题。这类问题变化繁多，解法各异。论文归纳总结出了几种常用模型，我们将对它们做简要分析。1.最大区间调度问题数轴上有n个区间，选出最多的区间，使得这些区间不互相重叠。算法：按右端点坐标排序依次选择所有能选的区间2.多个资源的调度问题有n个区间和无限多的资源，每个资源上的区间之间不互相重叠。将每个区间都分配到某个资源中，使用到的资源数量最小。定义区间集合深度d为包含任意一点的区间数量的最大值至少需要d个资源算法1：计算出d按左端点坐标排序依次将区间任意地分配到d个资源中实现记录每个资源的最大右端点用二叉堆维护这些坐标O(nd)O(nlogd)算法2：计算d（也可以不用计算）按右端点坐标排序每个区间都分配到右端点坐标最大的可用资源中。平衡二叉树O(nlogd)3.有最终期限的区间调度问题有n个长度固定、但位置可变的区间，将它们全部放置在[0,+∞)上。每个区间有两个已知参数：长度ti和最终期限di，设fi为其右端点坐标。定义放置所有区间，使它们不互相重叠且最大延迟L最小。iiiiiiidfifdfifdfl0inilL1max算法：按最终期限排序顺序安排各区间最终期限di4.最小区间覆盖问题有n个区间，选择尽量少的区间，使得这些区间完全覆盖某线段[s,t]。算法：按左端点坐标排序每次选择覆盖点s的区间中右端点坐标最大的一个，并更新s直到所选区间已包含t5.带权区间调度、覆盖问题例题：USACO2005decsilver仓库从第M秒到第E秒的任意时刻都需要有人打扫。有N个工人，每人给出自己的工作时间段：从第T1秒到第T2秒，需要支付工资S元。录用一部分人，要保证从M秒到第E秒的任意时刻都得有人打扫，问最少要付多少工资。转化问题转化为：在一些带权区间中，选出一部分，使它们覆盖[M,E]上的所有整数点，求权和最小值。算法：按右端点坐标排序，做动态规划状态：f[i]=覆盖[M,T2i]的权和最小值方程：iiiiiiijijTTMifSTTMifSTTjfMinif2,12,1112|][1优化1建立线段树[M,E]得到f[i]插入在T2i处计算f[i]：选取区间[T1i-1,T2i-1]中的最小值进行状态转移优化2建立一个栈保持栈中区间f值的单调性状态转移二分查找：O(logN)栈的维护：O(N)优化3按左端点坐标排序维护一个二叉堆，以f值为关键字状态转移（删除右端点坐标太小的区间）6.区间和点的有关问题有n个区间，m个点。若某区间包含了某点，则构成一对匹配关系。选出最多的区间和相同数量的点，使对应的区间和点构成匹配关系。算法：所有点按坐标排序选取包含该点且右端点坐标最小的区间优化按区间左端点排序，得到有序表维护二叉堆，以区间右端点为关键字所有点按坐标从小到大依次处理维护二叉堆：插入左端点小于等于该点坐标的区间删除右端点小于该点坐标的区间取出右端点坐标最小的与该点匹配并删除总结有序性算法的选择优化——数据结构的选择