FatMouse' Trade （贪心）

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

题意：就是说给出钱数，然后去买更多的豆豆，每种豆豆可以不买完。。

思路：贪心。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 struct node
 5 {
 6     double a,b,c;
 7 }ch[10001],cha ;
 8 int main()
 9 {
10     int m,n;
11     while(scanf("%d %d",&m,&n)&&(m != -1)&&(n != -1))
12     {
13         double sum = 0 ;
14         for(int i = 0 ; i <= n-1 ; i++)
15         {
16             scanf("%lf %lf",&ch[i].a,&ch[i].b);
17         }
18         for(int i = 0 ; i <= n-1 ; i++)
19         {
20             if(ch[i].b == 0)
21             {
22                 sum += ch[i].a ;//如果某一种的所需钱数为0，那么就先买这种
23                 ch[i].b = -1 ;//买完了就要进行标记，以后防止第二次重复被买。。。
24             }
25         }
26         for(int i = 0 ; i <= n-1 ; i++)
27         ch[i].c = ch[i].a/ch[i].b ;//求出每样豆子的性价比，这样来比较得出先买哪样
28         for(int i = 0 ; i <= n-2 ; i++)
29         {
30             for(int j = 0 ; j <= n-2-i ; j++)
31             {
32                 if(ch[j].c < ch[j+1].c)
33                 {
34                     cha = ch[j] ;
35                     ch[j] = ch[j+1] ;
36                     ch[j+1] = cha ;
37                 }
38             }
39         }
40         for(int i = 0 ; i <= n-1 ; i++)
41         {
42             if(ch[i].b != -1)
43             {
44                 if(m >= ch[i].b)
45                 {
46                     m -= ch[i].b ;
47                     sum += ch[i].a;
48                 }
49                 else
50                 {
51                     sum += ch[i].c*m ;
52                     break ;
53                 }
54             }
55         }
56         printf("%.3lf\n",sum) ;
57     }
58     return  0 ;
59 }

View Code