首页 > 代码库 > 贪心/hdu 1009 FatMouse' Trade

贪心/hdu 1009 FatMouse' Trade

题意

  有n种物品,每一种需要不同的消费,现在手里有m块钱,求问最多可以买多少

分析

  贪心

  把每一种物品的价格算出来,然后sort一下,按照价格从便宜到贵排序,能买多少买多少,买买买!

Accepted Code

 1 /* 2     PROBLEM:hdu1009 3     AUTHER:Nicole Lam 4     MEMO:贪心 5 */ 6  7 #include<cstdio> 8 #include<algorithm> 9 using namespace std;10 11 12 struct xx13 {14     double j,f,price;15 };16 xx x[1010];17 18 19 20 bool cmp(xx a,xx b)21 {22     if (a.price <= b.price) return true;23     return false;24 }25 26 27 int main()28 {29     int m,n;30     scanf("%d%d",&m,&n);31     while ( m!=-1  &&  n!=-1)32     {33         for (int i=1;i<=n;i++)34         {35             scanf("%lf%lf", &x[i].j, &x[i].f);36             x[i].price = x[i].f / x[i].j;37         }38         sort(x+1,x+1+n,cmp);39 40         double ans = 0;41 42         for (int i=1;i<=n;i++)43         {44             if (m>=x[i].f)45             {46                 m-=x[i].f;47                 ans+=x[i].j;48             }49             else50             {51                 ans+=m*x[i].j/x[i].f;52                 m=0;53                 break;54             }55         }56         printf("%.3lf\n",ans);57         scanf("%d%d", &m, &n);58     }59     return 0;60 }

 

贪心/hdu 1009 FatMouse' Trade