随笔 - 21  文章 - 0  trackbacks - 0
<2009年2月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
1234567

常用链接

留言簿(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 蔗晨 阅读(1068) 评论(0)  编辑 收藏 引用

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