posts - 43,  comments - 9,  trackbacks - 0
Two Professors
CERC 2008

题目大意:给n条线段,要求划分成尽可能少的子集,使得在同一个子集中的线段两两不重叠.
同时限定线段1和线段2不能在同一子集中.

记每条线段为[Li,Ri], 每个子集的最右端为Bi.
记线段1和2中,L较小的那个为X,另一个为Y.

如果没有那个限定,容易想到贪心的方法:将所有线段按L从小到大排序.然后依次处理线段k,如果当前存在某个集合的Bi<=Lk,就将Lk加入此集合中,并更新Bi=Rk.否则新开一个集合放入k.模拟这个过程,最后的集合数就是答案.用堆维护已有集合的信息,时间复杂度是O(nlgn).

有了限制条件后,原方法不适用了,因为在X与Y之间处理的线段,对Y有后效性.这会使得单纯按照刚才的方法随意贪心,可能轮到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就是关键先生.

所以只需稍微改造之前的算法,在处理X与Y之间的线段时,判断并记录下是否出现过可选局面.这样就能正确处理Y遭遇X的情形了.
其它情形时策略不变(可以证明这样的解是最优的).

代码略...

posted on 2009-12-24 14:34 wolf5x 阅读(479) 评论(1)  编辑 收藏 引用 所属分类: acm_icpc

FeedBack:
# re: Two Professors (CERC 2008) 解题报告
2009-12-31 21:17 | zaakdov
Up!  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

"Do not spend all your time on training or studying - this way you will probably become very exhausted and unwilling to compete more. Whatever you do - have fun. Once you find programming is no fun anymore – drop it. Play soccer, find a girlfriend, study something not related to programming, just live a life - programming contests are only programming contests, and nothing more. Don't let them become your life - for your life is much more interesting and colorful." -- Petr

留言簿(3)

随笔分类(59)

随笔档案(43)

cows

搜索

  •  

最新评论

评论排行榜