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 ysg860607 at 2008-09-20 01:27:04 on Problem 1716
In Reply To:贪心算法 谁帮看以下为什么不过呀 Posted by:ryangiggsy at 2007-08-16 16:34:08
> 每次选取在所有区间中出现次数最多的数字 结果总是wa
> #include"stdio.h"
> #include"stdlib.h"
> #include"string.h"
> int a[10001];
> int b[10001];
> int c[10001];
> int yong[10001];
> int main()
> { int n;
>   scanf("%d",&n);
>   int sum;
>   memset(yong,0,sizeof(yong));
>   memset(c,0,sizeof(c));
>   int i,j;
>   int max1=-1,min1=10001;
>   int max,maxi;
>   for(i=0;i<n;i++)
>   {scanf("%d%d",&a[i],&b[i]);
>    for(j=a[i];j<=b[i];j++)
>    yong[j]++;
>   }
>   sum=0;
>   int biaozhi=0;
>   while(biaozhi!=n)
>   {   max=0;
> 	  for(i=0;i<=10000;i++)
> 	  if(yong[i]>max) {max=yong[i],maxi=i;}
> 	  yong[maxi]=-1;
> 	  sum++;
> 	  for(i=0;i<n;i++)
> 	  if(c[i]<2&&maxi>=a[i]&&maxi<=b[i]) 
> 	  {c[i]++;
>        if(c[i]==2) 
> 	   {biaozhi++;
> 		for(j=a[i];j<=b[i];j++)
>         yong[j]--;}
> 	  }
>   }
>   printf("%d\n",sum);
>   return 0;
>   
> }

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