hdu 1.3.1 FatMouse' Trade

贪心的运用，主要看其比值，取最大值实现贪心...
 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<vector>
 4 using namespace std;
 5 
 6 struct room
 7 {
 8     int j;
 9     int f;
10     bool operator < (const room t)const
11     {
12         return (float)j/f >(float)t.j/t.f;
13     }
14 };
15 
16 int main()
17 {
18     //freopen("input.txt","r",stdin);
19     int m,n,i;
20     double ans;
21     while(scanf("%d%d",&m,&n) && (m+1) &&(n+1))
22     {
23         vector<room> v;
24         room r;
25         ans = 0;
26         for(i = 0; i < n; i++)
27         {
28             scanf("%d%d",&r.j,&r.f);
29             v.push_back(r);
30         }
31         sort(v.begin(),v.end());
32 
33         i = 0;
34         while(m > 0 && i < v.size())
35         {
36             if(v[i].f <= m)
37             {
38                 m -= v[i].f;
39                 ans += v[i].j;
40             }
41             else
42             {
43                 ans += (double)(v[i].j* m)/v[i].f ;
44                 m = 0;//½áÊø
45             }
46             i++;
47         }
48         printf("%.3lf
",ans);
49     }
50 
51     return 0;
52 }