題目：
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 52127 Accepted Submission(s):
17505
Input The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1's. All integers are not greater than 1000.
Output For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.
Sample Input 5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1
Sample Output 13.333 31.500 分析：本題用到的是貪心算法，貓糧換成Java豆的比例越大應越先被兌換。在此我通過每個結構體保存每個屋子中的J[i]與F[i]及其兌換比例scale,然後利用sort將所有結構體中的scale按從大到小進行排序。之所以這樣做的原因是，根據scale排序後，不會打亂原先每個屋子J[i]與F[i]及其兌換比例scale的對應關系,即排序的過程中結構體的結構不發生變換，只不過是根據結構體這種的scale變量給所有結構體排一下序而已。最後的換Java豆的工作也簡單多了。 代碼如下：
1 #include<cstdio>
2 #include<algorithm>
3 using namespace std;
4
5 const int maxN = 1000 + 5;
6
7 struct warehouse{
8 int J;
9 int F;
10 double scale;
11 }House[maxN];
12
13 bool cmp(const struct warehouse a, const struct warehouse b) {
14 return a.scale > b.scale;
15 }
16
17 int main() {
18 int M, N;
19 double ans;
20 while(scanf("%d %d", &M, &N) == 2){
21 if(M == -1 && N == -1) break;
22 //輸入
23 for(int i = 0; i < N; i++) {
24 scanf("%d %d", &House[i].J, &House[i].F);
25 House[i].scale = (double)House[i].J/House[i].F;
26 }
27 //將所有屋子中的貓糧與Java豆兌換的比例排序
28 sort(House, House + N, cmp);
29 // for(int i = 0; i < N; i++)
30 // printf("%.3lf\t", House[i].scale);
31 //按比例從大到小分配貓糧
32 ans = 0.0;
33 int pos = 0;
34 while(M > 0 && N > 0){//貓糧換完，或者Java豆已經沒有時應該終止循環
35 if(M > House[pos].F)
36 ans += House[pos].J; //若貓糧充足，直接將屋子的Java豆兌換下來
37 else
38 ans += (double)House[pos].J * M / House[pos].F; //能兌換的貓糧不足，這時應該按比例來兌換Java豆
39 M -= House[pos].F;
40 N--;
41 pos++;//到下一家
42 }
43 //輸出
44 printf("%.3lf\n", ans);
45 }
46 return 0;
47 }
2015-07-02文
