随笔 - 21 文章 - 0 trackbacks - 0

2009年2月

日

一

二

三

四

五

六

25

26

27

28

29

30

31

1

2

3

4

5

8

9

14

15

16

17

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

常用链接

留言簿(1)

随笔分类

随笔档案

新闻档案

2009年3月 (1)

搜索

最新评论

阅读排行榜

评论排行榜

最少区间覆盖问题

关于区间的往往可以贪心。
pku2376
用最少的线段覆盖一条大线段。
按左边的坐标排序，找左边符合开始的线段中右边最大的。

sort(a,a+n);

end=1;

i=0;

tp=-1;

cnt=0;

while(end<=T)

{

if(i>n||cnt>n)

{

printf("-1\n");

return 0;

}

if(a[i].l<=end)

{

if(tp<=a[i].r)

{

tp=a[i].r;

}

i++;

if(tp>=T)

{

cnt++;

break;

}

}

else

{

end=tp+1;

cnt++;

tp=-1;

}

}

posted on 2009-02-18 09:31 蔗晨阅读(1082) 评论(0) 编辑收藏引用

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！



网站导航: 博客园 IT新闻 BlogJava 知识库博问管理