算法合集之《浅谈信息学竞赛中的区间问题》.ppt

《算法合集之《浅谈信息学竞赛中的区间问题》.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、浅谈信息学竞赛中的区间问题华东师大二附中周小博引言在信息学竞赛中，有很多问题最终都能转化为区间问题。这类问题变化繁多，解法各异。论文归纳总结出了几种常用模型，我们将对它们做简要分析。证明没给出，可在论文中找到1.最大区间调度问题数轴上有n个区间，选出最多的区间，使得这些区间不互相重叠。算法：按右端点坐标排序依次选择所有能选的区间2.多个资源的调度问题有n个区间和无限多的资源，每个资源上的区间之间不互相重叠。将每个区间都分配到某个资源中，使用到的资源数量最小。定义区间集合深度d为包含任意一点的区间数量的最大值至少需要d个资源算法1：计算出d按左端点坐标排序依次将区间任意地分

2、配到d个资源中可以证明每个区间都能分配到资源实现记录每个资源的最大右端点用二叉堆维护这些坐标O(nd)O(nlogd)其实这里可以不用计算d的值不断添加新资源算法2：计算d（也可以不用计算）按右端点坐标排序每个区间都分配到右端点坐标最大的可用资源中。平衡二叉树O(nlogd)实现麻烦,但能解决更多问题3.有最终期限的区间调度问题有n个长度固定、但位置可变的区间，将它们全部放置在[0,+∞)上。每个区间有两个已知参数：长度ti和最终期限di，设fi为其右端点坐标。定义放置所有区间，使它们不互相重叠且最大延迟L最小。算法：按最终期限排序顺序安排各区间最终期限di4.最小区间

3、覆盖问题有n个区间，选择尽量少的区间，使得这些区间完全覆盖某线段[s,t]。算法：按左端点坐标排序每次选择覆盖点s的区间中右端点坐标最大的一个，并更新s直到所选区间已包含tMax5.带权区间调度、覆盖问题动态规划优化线段树平衡二叉树并查集栈单调决策二叉堆例题：USACO2005decsilver仓库从第M秒到第E秒的任意时刻都需要有人打扫。有N个工人，每人给出自己的工作时间段：从第T1秒到第T2秒，需要支付工资S元。录用一部分人，要保证从M秒到第E秒的任意时刻都得有人打扫，问最少要付多少工资。转化问题转化为：在一些带权区间中，选出一部分，使它们覆盖[M,E]上的所有整数点

4、，求权和最小值。算法：按右端点坐标排序，做动态规划状态：f[i]=覆盖[M,T2i]的权和最小值方程：优化1建立线段树[M,E]得到f[i]插入在T2i处计算f[i]：选取区间[T1i-1,T2i-1]中的最小值进行状态转移线段树时间复杂度O(Nlog(E-M))优化2建立一个栈保持栈中区间f值的单调性状态转移二分查找：O(logN)栈的维护：O(N)单调决策时间复杂度O(NlogN)优化3二叉堆按左端点坐标排序维护一个二叉堆，以f值为关键字状态转移（删除右端点坐标太小的区间）总时间复杂度O(NlogN)6.区间和点的有关问题有n个区间，m个点。若某区间包含了某点，则

5、构成一对匹配关系。选出最多的区间和相同数量的点，使对应的区间和点构成匹配关系。二分图匹配？太慢算法：所有点按坐标排序选取包含该点且右端点坐标最小的区间时间复杂度O(nm)优化按区间左端点排序，得到有序表维护二叉堆，以区间右端点为关键字所有点按坐标从小到大依次处理维护二叉堆：插入左端点小于等于该点坐标的区间删除右端点小于该点坐标的区间取出右端点坐标最小的与该点匹配并删除有序表二叉堆时间复杂度O(nlogn+mlogm)总结有序性算法的选择优化——数据结构的选择谢谢！