《浅谈信息学竞赛中的区间问题》由会员分享，可在线阅读，更多相关《浅谈信息学竞赛中的区间问题（21页珍藏版）》请在金锄头文库上搜索。
1、浅谈信息学竞赛中的浅谈信息学竞赛中的区间问题区间问题引言引言 n n在信息学竞赛中，有很多问题最终都能转在信息学竞赛中，有很多问题最终都能转化为区间问题。化为区间问题。n n这类问题变化繁多，解法各异。论文归纳这类问题变化繁多，解法各异。论文归纳总结出了几种常用模型，我们将对它们做总结出了几种常用模型，我们将对它们做简要分析。简要分析。1.最大区间调度问题最大区间调度问题n n数轴上有数轴上有n个区间，选出最多的区间，使得个区间，选出最多的区间，使得这些区间不互相重叠。这些区间不互相重叠。n n算法：算法：n n按右端点坐标排序按右端点坐标排序n n依次选择所有能选的区间依次选择所有能选的区间
2、2.多个资源的调度问题多个资源的调度问题n n有有n个区间和无限多的资源，每个资源上的个区间和无限多的资源，每个资源上的区间之间不互相重叠。将每个区间都分配区间之间不互相重叠。将每个区间都分配到某个资源中，使用到的资源数量最小。到某个资源中，使用到的资源数量最小。 n n定义区间集合深度定义区间集合深度d为包含任意一点的区间为包含任意一点的区间数量的最大值数量的最大值n n至少需要至少需要d个资源个资源n n算法算法1 1：n n计算出计算出dn n按左端点坐标排序按左端点坐标排序n n依次将区间任意地分配到依次将区间任意地分配到d个资源中个资源中实现实现n n记录每个资源的最大右端点记录每个
3、资源的最大右端点n n用二叉堆维护这些坐标用二叉堆维护这些坐标n nO(nd)n nO(nlogd)算法算法2：n n计算计算d（也可以不用计算）（也可以不用计算）n n按右端点坐标排序按右端点坐标排序n n每个区间都分配到右端点坐标最大的可用每个区间都分配到右端点坐标最大的可用资源中。资源中。 n n平衡二叉树平衡二叉树O(nlogd)3.有最终期限的区间调度问题有最终期限的区间调度问题n n有有n个长度固定、但位置可变的区间，将它个长度固定、但位置可变的区间，将它们全部放置在们全部放置在0,+)上。每个区间有两上。每个区间有两个已知参数：长度个已知参数：长度ti和最终期限和最终期限di，设
4、，设fi为为其右端点坐标。定义其右端点坐标。定义n n放置所有区间，使它们不互相重叠且最大放置所有区间，使它们不互相重叠且最大延迟延迟L最小。最小。 n n算法：算法：n n按最终期限排序按最终期限排序n n顺序安排各区间顺序安排各区间最终期限最终期限di4.最小区间覆盖问题最小区间覆盖问题n n有有n个区间，选择尽量少的区间，使得这些个区间，选择尽量少的区间，使得这些区间完全覆盖某线段区间完全覆盖某线段s,t。n n算法：算法：n n按左端点坐标排序按左端点坐标排序n n每次选择覆盖点每次选择覆盖点s的区间中右端点坐标最大的区间中右端点坐标最大的一个，并更新的一个，并更新sn n直到所选区间
5、已包含直到所选区间已包含t5.带权区间调度、覆盖问题带权区间调度、覆盖问题例题：例题：USACO 2005 dec silvern n仓库从第仓库从第M秒到第秒到第E秒的任意时刻都秒的任意时刻都需要有人打扫。有需要有人打扫。有N个工人，每人个工人，每人给出自己的工作时间段：从第给出自己的工作时间段：从第T1秒秒到第到第T2秒，需要支付工资秒，需要支付工资S元。元。n n录用一部分人，要保证从录用一部分人，要保证从M秒到第秒到第E秒的任意时刻都得有人打扫，问最秒的任意时刻都得有人打扫，问最少要付多少工资。少要付多少工资。转化转化n n问题转化为：在一些带权区间中，选出一问题转化为：在一些带权区间
6、中，选出一部分，使它们覆盖部分，使它们覆盖M,E上的所有整数点，上的所有整数点，求权和最小值。求权和最小值。 n n算法：按右端点坐标排序，做动态规划算法：按右端点坐标排序，做动态规划n n状态：状态：fi=覆盖覆盖M,T2i的权和最小值的权和最小值 n n方程：方程：优化优化1n n建立线段树建立线段树M,E n n得到得到fi插入在插入在T2i处处n n计算计算fi：选取区间：选取区间T1i-1,T2i-1中的最小值进行状态转移中的最小值进行状态转移 优化优化2n n建立一个栈建立一个栈n n保持栈中区间保持栈中区间f值的单调性值的单调性n n状态转移状态转移二分查找：二分查找：O(log
7、N)n n栈的维护：栈的维护：O(N)优化优化3n n按左端点坐标排序按左端点坐标排序n n维护一个二叉堆，以维护一个二叉堆，以f值为关键字值为关键字n n状态转移状态转移（删除右端点坐标太小的区间）（删除右端点坐标太小的区间）6.6.区间和点的有关问题区间和点的有关问题n n有有n个区间，个区间，m个点。若某区间包含了某点，个点。若某区间包含了某点，则构成一对匹配关系。选出最多的区间和则构成一对匹配关系。选出最多的区间和相同数量的点，使对应的区间和点构成匹相同数量的点，使对应的区间和点构成匹配关系。配关系。 算法：算法： n n所有点按坐标排序所有点按坐标排序n n选取包含该点且右端点坐标最小的区间选取包含该点且右端点坐标最小的区间优化优化n n按区间左端点排序，得到有序表按区间左端点排序，得到有序表n n维护二叉堆，以区间右端点为关键字维护二叉堆，以区间右端点为关键字n n所有点按坐标从小到大依次处理所有点按坐标从小到大依次处理维护二叉堆：维护二叉堆：插入左端点小于等于该点坐标的区间插入左端点小于等于该点坐标的区间删除右端点小于该点坐标的区间删除右端点小于该点坐标的区间取出右端点坐标最小的与该点匹配并删除取出右端点坐标最小的与该点匹配并删除 总结总结n n有序性有序性n n算法的选择算法的选择n n优化优化数据结构的选择数据结构的选择
