首页 > 代码库 > hdoj 4310 贪心

hdoj 4310 贪心

不知为毛,过不了

我的代码:

#include<stdio.h>

int main()
{
 int n,a[30],b[30],temp,i,j,s1,s2;
 double c[30];
 while(scanf("%d",&n)!=EOF)
 {
  s1=0;
  s2=0;
  for(i=0;i<n;i++)
  {
   scanf("%d%d",&a[i],&b[i]);
   s1+=a[i];
   c[i]=a[i]/b[i];
  }
     for(i=0;i<n;i++)
  {
   for(j=i+1;j<n;j++)
   {
    if(c[i]<c[j])
    {
     temp=c[i];
     c[i]=c[j];
     c[j]=temp;
     temp=b[i];
     b[i]=b[j];
     b[j]=temp;
     temp=a[i];
     a[i]=a[j];
     a[j]=temp;
    }
   }
  }
  for(i=0;i<n;i++)
  {
      s2+=s1*b[i];
   s1-=a[i];
  }
  printf("%d\n",s2);
 }
}

 Ac的代码:

  1. #include <stdio.h>   
  2. #include <algorithm>   
  3. using namespace std;  
  4.   
  5. struct Node  
  6. {  
  7.     int dps;  
  8.     int hp;  
  9. }a[30];  
  10.   
  11. int cmp(Node x,Node y)  
  12. {  
  13.     return x.hp*y.dps<y.hp*x.dps;//按比率排,避免小数,所以讲式子进行转换   
  14. }  
  15.   
  16. int main()  
  17. {  
  18.     int t,i;  
  19.     int sum,ans;  
  20.     while(~scanf("%d",&t))  
  21.     {  
  22.         sum = ans = 0;  
  23.         for(i = 0;i<t;i++)  
  24.         {  
  25.             scanf("%d%d",&a[i].dps,&a[i].hp);  
  26.             sum+=a[i].dps;  
  27.         }  
  28.         sort(a,a+t,cmp);  
  29.         for(i = 0;i<t;i++)  
  30.         {  
  31.             ans+=sum*a[i].hp;  
  32.             sum-=a[i].dps;  
  33.         }  
  34.         printf("%d\n",ans);  
  35.     }  
  36.   
  37.     return 0;  
  38. }  
  39. 有毛区别