111qqz的小窝

老年咸鱼冲锋!

codeforces edu #29 E. Turn Off The TV (思维,乱搞)

题目链接

题意:有若干线段,给出起点和终点,问是否有一个线段是冗余的。冗余的意思是说,对于该线段所覆盖的所有整数点,没有该线段,也能被其他一个或者多个线段覆盖到。如果有,输出任意一个冗余线段即可。

思路:画画图? 显然可以按照第一关键字左端点升序,第二关键字右端点降序(降序是为了处理 n=2,[1,2],[1,3] 这样的case容易一些),先考虑2种最简单的情况。

第一种是a[i+1]完全被a[i]包裹在里面,准确得说不一定是a[i],而是之前所有线段的最大右端点的那条线段,此时a[i+1]就是冗余的线段。

第二种是a[i+1]的左端点在之前所有线段的最大右端点右边,此时没有冗余,继续进行。

接下来考虑比较复杂的相交情况,我们画图发现,当前线段是否冗余,只与a[i-1]和a[i+1]有关。

如果第i条线段的左端点,不超过第i-2条线段的右端点的右边一个位置,此时第i-1条线段就是冗余的。

wa了2次。。原因是没认真看题,l,r的范围的最小值是从0开始而不是1。所以总体来说是道水题(调教场的题这么水了么。。。

 

 

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz