| ||||||||||
| 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:贪心算法 谁帮看以下为什么不过呀 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator