1,题目大意:
给n条线段,要求划分成尽可能少的子集,使得在同一个子集中的线段两两不重叠.
同时限定线段1和线段2不能在同一子集中.
2,问题分析:
(1)
记每条线段为[Li,Ri], 每个子集的最右端为Bi.
记线段1和2中,L较小的那个为X,另一个为Y.
(2)
如果没有那个限定,容易想到贪心的方法:
将所有线段按L从小到大排序.然后依次处理线段k,如果当前存在某个集合的Bi<=Lk,就将Lk加入此集合中,并更新Bi=Rk.否则新开一个集合放入k.模拟这个过程,最后的集合数就是答案.用堆维护已有集合的信息,时间复杂度是O(nlgn).
(3)
有了限制条件后,原方法不适用了,因为在X与Y之间处理的线段,对B有后效性.这会使得单纯按照刚才的方法随意贪心,可能轮到Y时,只有X所在集合的Bi<=LY,迫使必须开新集合.但实际上,有可能可以通过调整X与Y之间的线段排列结构,使Y避开X.
问题关键就是如何判断能否调整(并不用关心详细的调整步骤).
当一条线段(P)面临多个可插入的集合时,之前的方法是随意选一个,而不合适的决策正在此产生.下面构造一个情景:
假设P可以在两个集合s,t中选择,而X在s中.
现在P选择加入t.
接下来按部就班地处理.
轮到Y选时,它只能选择加入s,或者开新的集合.
这时候,我们能得知,如果当初P选择的是s,紧随其后的其它选择也相应地对调,那么Y此时肯定面临的是只能加入t,或者开新的集合.
这样Y当然直接加入t就行了.
这说明,只要存在一个这样的P,当Y遭遇X时,肯定存在形状对称的另一个局面使Y避开X,而P就是关键先生.
(4)
所以只需稍微改造之前的算法,在处理X与Y之间的线段时,判断并记录下是否出现过可选局面.这样就能正确处理Y遭遇X的情形了.
其它情形时策略不变(可以证明这样的解是最优的).
题目连接:
http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1517
分享到:
相关推荐
教授推荐信模板Professors Recommendation Letters(英文版)
1. Professors can teach the same course in several semesters, and each offering
Professors' and teachers' views of competencies necessary for mainstreaming Psychology in the Schoolr 1982, / 9 , 402-407 PROFESSORS’ AND TEACHERS’ VIEWS OF COMPETENCIES NECESSARY FOR ...
语言:English 显示我的教授Rit教授的评级,同时搜索虎中心和CSH日程表制作人的课程。 教授的名字现在将链接到他们的教授页面(或...GitHub Repo在这里:https://github.com/calvinwu4/rit-rate-my-professors-extension
1.3.2版*添加了一个弹出窗口,其中包含有关教授的更多详细信息,因此您无需单击链接!该数字基于最近的20条评论,因此可能与“为我的教授评分”数字略有不同 *错误修复单击您教授旁边的评分,转到其“为我的教授...
语言:English (United States) 将RateMyProfessors评级直接输入到Vanderbilt类别搜索中。 在班级搜索中直接查看您要搜索的老师的RateMyProfessors评分。 ... 请注意,此扩展程序不适用于有多位老师的课程。...
语言:English (United States) 将RateMyProfessors评分直接放入康奈尔大学班级名册。 “评估我的康奈尔教授”自动从“评估我的教授”到康奈尔班级名册中显示每个教授的评估。 此扩展程序不是在选项卡之间切换,而是...
无需离开页面即可查看“为我的教授信息评分”! 不要浪费时间搜索每位教授,请查看大学课程目录旁边的“对我的教授进行评级(RMP)”! 支持语言:English
This second edition of the Essentials version is based on the recent...professors who want a shorter text and do not cover all the topics in the ninth edition.The new second edition of Essentials will be...
UiucProfessors 搜索教授信息 待办事项 设计 同名教授(可能对此无能为力) 我看到的其他任何东西 使用说明 有两个任务应该每学期运行一次。 应首先运行“课程”解析器以建立课程列表,然后应运行“教授”解析...
语言:English 在搜索课程时显示“对我的教授的评价”对教授的评价。 ... 教授的姓名将链接到其“评价我的教授”页面(如果找不到,则显示搜索结果)。 ... (“对我的教授的评价”中最有帮助的评级始终具有“极好的”总体...
Applications follow, starting with the simplest ones (two-level systems, the harmonic oscillator, etc.), and becoming gradually more complicated (the hydrogen atom, approximation methods, etc.)....
RIT评价我的教授扩展该扩展名显示了... 例如,在RIT的课程搜索中的Thomas Reichlmayr在Rate My Professors中被作为Tom Reichlmayr找到。 最后,有一个文件,用于自定义昵称(例如,Thiagarajah Arujunan应该引用Al Aru
Artificial neural networks may probably be the single most successful technology in the last two decades which has been widely used in a large variety of applications. The purpose of this book is to ...
将RateMyProfessors评级直接纳入Vanderbilt Class Search。 在班级搜索中直接查看您要搜索的老师的RateMyProfessors评分。...请注意,此扩展程序不适用于有多位老师的课程 v1.1.2-修复了具有相同姓氏和名字的两位教师...
Intended for graduate students, professors and academic researchers in the fields of aerospace and mechanical engineering, mathematics, astronomy and astrophysics, Spacecraft Formation Flying is a ...
大学注册Epicodus第4周高级数据库分配,2015年9月2日Summer Brochtrup和Aimee Reiss描述用户可以在该网站上添加/删除课程,学生和教授,按名称搜索内容以及将学生添加/删除课程和相关教授的网站。...
任何学费我的教授扩展 此扩展名显示了从众包的在网站上搜索课程时对教授的“对评分”的评分。 描述 教授的姓名将链接到他们的“为我的教授评分”页面(如果未找到,则为搜索结果)。... (“对我的教授的评价”中最有...