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