hdu 1009 FatMouse' Trade （动态规划之贪心）

http://acm.hdu.edu.cn/showproblem.php?pid=1009

View Code

 1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 struct Trade
 6 {
 7     int j,f;
 8     double percent;
 9 }mouse[3001];
10 bool cmp(Trade a,Trade b)
11 {
12     return a.percent>b.percent;
13 }
14 int main()
15 {
16     int m,n,i;
17     double sum;
18     while(scanf("%d%d",&m,&n),m!=-1||n!=-1)
19     {
20         for(i=0;i<n;i++)
21         {
22             scanf("%d%d",&mouse[i].j,&mouse[i].f);
23             mouse[i].percent=1.0*mouse[i].j/mouse[i].f;
24         }
25         sort(mouse,mouse+n,cmp);
26         sum=0;
27         for(i=0;i<n;i++)
28         {
29             if(m>mouse[i].f)
30             {
31                 sum+=mouse[i].j;
32                 m-=mouse[i].f;
33             }
34             else
35             {
36                 sum+=mouse[i].percent *m;
37                 m=0;
38                 break;
39             }
40         }
41         printf("%.3f\n",sum);
42     }
43     return 0;
44 }