《浅谈信息学竞赛中的区间问题.ppt》由会员分享，可在线阅读，更多相关《浅谈信息学竞赛中的区间问题.ppt（21页珍藏版）》请在三一文库上搜索。
1、嘉 齐 茹 沛 籽 纲 柔 摹 楷 贱 谍 灌 伏 块 手 费 啤 揭 挟 纺 真 纹 啮 抢 奶 针 杂 吕 乎 容 奸 睬 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅谈信息学竞赛中的区间问题 冯 梅 致 岁 可 抽 蜀 跟 夺 曲 康 憋 琼 砸 扦 诸 牢 愤 衣 诌 乃 邮 翠 郊 宗 滤 渝 近 瓦 虱 涟 妨 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 引言 n在信息学竞赛中，有很多问题最终都能转 化为区间问题。 n这类问题变化繁多，解法各异。论文归纳 总结出
2、了几种常用模型，我们将对它们做 简要分析。 鹿 讲 收 差 枉 柳 劫 万 蜜 批 切 蔗 档 源 祟 噶 河 诛 井 缮 栖 帖 记 僧 针 身 雀 吸 歼 笔 沈 吊 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 1.最大区间调度问题 n数轴上有n n个区间，选出最多的区间，使得 这些区间不互相重叠。 n算法： n按右端点坐标排序 n依次选择所有能选的区间 栓 薯 婶 昧 撰 岿 淆 挎 顷 忽 非 廷 牺 你 床 镶 捻 憾 晚 膜 唤 邢 翌 妨 患 茵 堑 碳 睫 避 侩 轨 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题
3、 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 2.多个资源的调度问题 n有n n个区间和无限多的资源，每个资源上的 区间之间不互相重叠。将每个区间都分配 到某个资源中，使用到的资源数量最小。 监 咙 摊 族 欢 润 嵌 爹 斜 另 晋 醇 滁 莹 误 氏 并 凡 看 痊 花 泼 瑞 态 莫 谐 救 履 钱 隅 击 啄 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 n定义区间集合深度d d为包含任意一点的区间 数量的最大值 n至少需要d d个资源 n算法1： n计算出d d n按左端点坐标排序 n依次将区间任意地分配到d个资源中
4、偏 凶 阐 刨 凭 墓 挎 烁 鸿 七 蔡 缔 澎 雀 襟 涯 潮 衔 爆 苍 频 丧 拥 纂 论 靡 嚼 姜 篆 备 窘 亨 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 实现 n记录每个资源的最大右端点 n用二叉堆维护这些坐标 n n O(nd)O(nd) n n O(nlogd)O(nlogd) 庐 反 粘 府 耍 达 些 慰 虚 箱 烤 辩 锈 孽 稠 犯 贮 氰 彪 庸 览 芽 感 霍 裤 磷 脑 化 瓷 扛 司 掺 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 算法2
5、： n计算d d（也可以不用计算） n按右端点坐标排序 n每个区间都分配到右端点坐标最大的可用 资源中。 n平衡二叉树O(nlogd)O(nlogd) 疡 羽 摹 弧 右 沪 勉 啪 累 哪 沮 推 巳 哨 垒 仟 基 妹 仁 灸 朗 听 旱 是 驭 薛 相 牡 聪 订 距 嵌 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 3.有最终期限的区间调度问题 n有n n个长度固定、但位置可变的区间，将它 们全部放置在0,+)上。每个区间有两 个已知参数：长度t t i i 和最终期限d d i i ，设f f i i 为 其右端点坐标。定义
6、n放置所有区间，使它们不互相重叠且最大 延迟L L最小。 粘 显 赴 帖 弓 主 澡 堤 畏 塘 醒 假 篮 宫 换 版 淹 宝 连 告 倔 修 藤 悸 解 浆 指 辽 颖 带 宰 他 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 n算法： n按最终期限排序 n顺序安排各区间 最终期限di 吹 成 台 败 秉 佐 剔 宇 拄 巫 蒸 钨 壁 豆 赘 嘘 佛 畔 捏 珊 算 楚 合 谭 唤 郑 歇 岸 镣 揩 澡 设 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 4.最小区间覆盖问
7、题 n有n n个区间，选择尽量少的区间，使得这些 区间完全覆盖某线段s,ts,t。 n算法： n按左端点坐标排序 n每次选择覆盖点s s的区间中右端点坐标最大 的一个，并更新s s n直到所选区间已包含t t 荡 万 雌 花 剐 苑 祥 秸 御 邹 浑 专 芯 饱 糜 诀 部 薛 婉 掉 磅 辖 戈 拎 碉 更 嚣 侣 惯 膘 靖 卿 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 5.带权区间调度、覆盖问题 洱 短 占 校 些 似 班 鹰 幽 赃 寄 淡 蚁 穴 锌 盆 鸡 档 塞 宛 俺 夺 骇 皆 晓 渣 谨 篱 绚 壬 洛 肝 浅
8、 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 例题：USACO 2005 dec silver n仓库从第MM秒到第E E秒的任意时刻 都需要有人打扫。有NN个工人，每 人给出自己的工作时间段：从第T1T1 秒到第T2T2秒，需要支付工资S S元。 n录用一部分人，要保证从MM秒到第 E E秒的任意时刻都得有人打扫，问最 少要付多少工资。 珊 隔 战 狄 会 靳 垂 辫 燎 秒 耸 罕 箍 揪 皋 翠 芒 洋 疏 忻 攻 盏 猾 果 魄 邓 旗 谐 挨 授 疹 惠 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞
9、 赛 中 的 区 间 问 题 转化 n问题转化为：在一些带权区间中，选出一 部分，使它们覆盖M,EM,E上的所有整数点 ，求权和最小值。 n算法：按右端点坐标排序，做动态规划 n状态：fi=fi=覆盖M,T2M,T2 i i 的权和最小值 n方程： 欺 篓 腊 脆 乾 栖 膜 荧 才 雾 泥 多 皋 亿 吹 狼 渭 蔬 拾 婆 妓 疑 罕 它 涤 耪 参 掉 玛 诣 幌 泼 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 优化1 n建立线段树M,EM,E n得到fifi插入在T2T2 i i 处 n计算fifi：选取区间T1T1 i i
10、-1,T2-1,T2 i i -1-1 中的最小值进行状态转移 汰 拥 糠 脉 衙 摩 绣 沥 拄 弥 笋 焦 惰 蛤 浑 稠 酉 太 惶 酋 驰 蹄 拽 冲 绢 锨 啊 损 馅 曹 必 趣 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 优化2 n建立一个栈 n保持栈中区间f f值的单调性 n状态转移二分查找：O(logN)O(logN) n栈的维护：O(N)O(N) 衡 肪 熬 托 甲 忙 递 哗 颂 耐 搬 畜 畜 坚 历 椅 搬 粱 娱 亭 臣 成 嫩 摊 近 种 钞 弊 咏 沫 抓 绰 浅 谈 信 息 学 竞 赛 中 的 区 间
11、 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 优化3 n按左端点坐标排序 n维护一个二叉堆，以f f值为关键字 n状态转移 （删除右端点坐标太小的区间） 獭 蔡 羹 扶 屯 夸 敲 颈 栋 旧 敖 莉 神 控 嘿 保 锋 脱 歉 挚 违 奄 尉 紫 湛 诸 诉 厩 遣 辛 荣 十 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 6.区间和点的有关问题 n有n n个区间，mm个点。若某区间包含了某点 ，则构成一对匹配关系。选出最多的区间 和相同数量的点，使对应的区间和点构成 匹配关系。 气 雏 胚 流 骚 涩 柑 雨 痘 伙
12、 勒 僚 誓 局 揪 考 纵 悼 茁 艾 啤 焦 换 婆 额 罕 聊 猖 免 集 或 凭 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 算法： n所有点按坐标排序 n选取包含该点且右端点坐标最小的区间 肆 涤 秸 想 罕 黄 赴 疵 瑶 酪 贝 役 拳 屑 柴 厌 粒 区 盯 操 蔽 怨 赤 侠 区 浇 陇 何 眯 粘 拖 糖 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 优化 n按区间左端点排序，得到有序表 n维护二叉堆，以区间右端点为关键字 n所有点按坐标从小到大依次处理 维
13、护二叉堆：维护二叉堆： 插入左端点小于等于该点坐标的区间插入左端点小于等于该点坐标的区间 删除右端点小于该点坐标的区间删除右端点小于该点坐标的区间 取出右端点坐标最小的与该点匹配并删除取出右端点坐标最小的与该点匹配并删除 截 植 潜 疙 枕 谜 回 涅 疚 坍 乓 骨 为 赁 绸 矣 涡 孕 特 颓 萄 拒 陪 扶 座 迅 现 禹 驹 廖 驼 台 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 总结 n有序性 n算法的选择 n优化数据结构的选择 谅 篷 娠 洒 袱 墅 蚂 纯 因 束 傻 窖 靠 耘 邻 瘫 酷 菲 檄 荧 亭 绒 芭 针 澄 骆 珍 拇 阿 戮 缘 觅 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 蛀 想 刷 歌 徒 愧 顿 谣 砸 湿 摆 统 醛 栋 豆 石 匣 手 耘 裹 唯 奈 凋 社 誓 频 咱 猜 纲 蹲 姚 俏 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题 浅 谈 信 息 学 竞 赛 中 的 区 间 问 题