| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
这方法对吗?In Reply To:这题0ms应该怎么做? Posted by:KosonLau at 2007-12-18 01:24:30 > 我的贪心过程如下:
>
> num=0;
> for(i=0;i<n;){
> num++;
> for(j=i+1;j<n;j++) //如果j区间的左边小于或等于i区的右边,则此区间可以覆盖
> if(check(p[j].l,p[i].r)!=1) continue;
> else break;
> i=j; //i跳转到下一个需要新增radar的区间
> }
> p的l是区间的左边,r是区间的右边
>
> o(n)时间,为什么还不能0ms??
这方法对吗?初想好像不对吧?如三个区间为(1,10)(2,3)(4,5),岂不是只需1个radar,但应需2个吧?
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator