Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这方法对吗?

Posted by temporary1 at 2009-08-17 14:48:35 on Problem 1328
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator