博客网 >

ZOJ1508的几种解法
作者:分类:默认分类标签:

题目的意思是给定n个区间,要求区间[ai, bi]里面取的数不能少于ci个,问最少取多少个可以满足条件。n最大值为50000,ai, bi的取值范围也是50000。现在设ai, bi的取值范围为m。

第一种解法是贪心。先把区间按右端点排序,每次取数的时候尽量往右边取。因为后面的区间的右端点比当前区间的右端点右,所以往右取可以保证结果是最优的。每次先要查询区间里面已经被取到的数的个数,然后不足的部分逐个取出。查询部分我是用线段树来统计实现的。快速找到区间里下一个还没取到的数我是通过一个类似并查集的结构实现的,记录每个数左边第一个没被取到的数,然像并查集的路径压缩那样优化。总的时间复杂度是O(nlogn+nlogm+mlogm),运行时间为320ms,其中读入和排序画了250ms。这是我第一个写的版本,用纯C写的,所以排序会慢一点实现较为复杂,代码量也有点大。

第二个做法是最常见的差分约束系统。这是我参考LeeMars的解题报告之后写的。以S[i]表示0到i之中取的个数,那么有S[i-1]+1>=S[i]>=S[i-1],S[ai]-S[bi-1]>=ci。把S[i]看成点,S[i]-S[j]>=t就连一条权值为t的有向边从点j指向点i,那么从S[-1]到S[i]的最长距离就是S[i]的最小值,可以通过bellman-ford来求解。但是点有O(m)个,边有O(m+n)条,直接做,即是加了Yen氏优化也是很可能超时的。这里LeeMars的解题报告里面说到了对这种线状的图的一种特殊的优化:在更新点的时候,先把往前的边更新一次,然后再把往后的边更新一次。这样确实快了很多,在用了和上一个方法一样的排序方法时也是320ms通过的。仔细分析这样做的复杂度,松弛操作最坏情况是要迭代O(n)次以后才会结束的,所以这个做法的复杂度是O(nlogn+nm)的。但是之所以可以这么快通过,我认为是数据比较弱的原因。

第三种解法有点像是前面两种的结合。考虑上面一种做法的S[i],S[i]是递增的,而且相邻两个之间最多相差1,所以每个约束的图像就是从S[bi-1]出发的水平线-斜线-水平线三段组成的折线,并且斜线的斜率都是一样的。S[i]就是经过这点的所有折线中的最大值,所以这种做法就是对区间按左端点排序后,从左往右扫描得到每个S[i]的值。因为只有线段左端点端点处的S[i]是需要用于更新后面的S[i],所以只需要求这n个S[i]以及最后的答案就可以了。在查询折线最大值的时候,我是用了一个优先队列来加速的。由于进入优先队列的每段折线第一段的水平线总会不低于当前的S[i],所以不需要记录这段的高度,为了避免这段高度的影响,我采用记录斜线在x轴上截距以及最后高度两个数来的方法来记录每个约束,这段折线在当前的S[i]个高度可以通过这两个数运算得到。最后总的时间复杂度是O(nlogn),在ZOJ上跑了230ms,不过这个是用C++写的,STL的sort比qsort要快一些,输入和排序只要180ms。

不过,上面的时间也是仅供参考的,因为还有更多的优化还没有加上去,例如用桶排代替快排。相信应该也会有更多更好其他的做法。

<< 我出过的题目 / 寒假见闻 >>

专题推荐

不平凡的水果世界

不平凡的水果世界

平凡的水果世界,平凡中的不平凡。 今朝看水果是水果 ,看水果还是水果 ,看水果已不是水果。这境界,谁人可比?在不平凡的水果世界里,仁者见仁,智者见智。

中国春节的那些习俗

中国春节的那些习俗

正月是农历新年的开始,人们往往将它看作是新的一年年运好坏的兆示期。所以,过年的时候“禁忌”特别多。当然,各个地方的风俗习惯不一样,过年的禁忌也是不一样的。

评论
0/200
表情 验证码:

VegetableB

  • 文章总数0
  • 画报总数0
  • 画报点击数0
  • 文章点击数0
个人排行
        博文分类
        日期归档