王道机试—例题 7.2 FatMouse’ Trade（简单贪心02）

例题 7.2 FatMouse’ Trade

题目描述：

FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.The warehouse has N rooms.

The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food.

FatMouse does not have to tradefor all the JavaBeans in the room, instead, he may get J[i]*a% pounds of JavaBeans if he pays F[i]*a% pounds of cat food. Here “a” is a real number. Now he is assigning this homework to you:tell him the maximum amount of

JavaBeans he can obtain.

输入：

The input consists of multiple test cases. Each test case begins with a line containing two non-negativeintegers 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.

输出：

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.

样例输入：

5 3

7 2

4 3

5 2

20 3

25 18

24 15

15 10

-1 -1

样例输出：

13.333

31.500

【题目大意】

老鼠准备了 M 磅猫粮，并且准备拿这些猫粮和守卫仓库的猫交换自己最爱的咖啡豆（JavaBean）。仓库共有 N 个房间，每个房间里面都有咖啡豆。在第 i 个房间内有 J[i]磅咖啡豆，但相应地需要付出 F[i]磅的猫粮才能进行兑换。但是，老鼠并不一定要兑换该房间内全部的咖啡豆；相反，如果老鼠支付 a%*F[i]的猫粮，那么可以获得 a%*J[i]的咖啡豆，这里阿a是一个实数。现在请你告诉它，M 磅猫粮最多可以获得多少咖啡豆。

【分析】：

1. 这和我们平时买东西是一个道理，要考虑性价比，每个房间的猫粮都对应着不同的价格（即咖啡豆）；

2. 因此，首先对不同房间的猫粮进行排序，性价比最高的在前面；然后把手上的咖啡豆花光即可获得最多的猫粮；

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 1000;
struct JavaBean {
    double weight;
    double cost;
};
JavaBean arr[MAXN];
bool Compare(JavaBean x, JavaBean y) {
     return (x.weight / x.cost) > (y.weight / y.cost);
}
int main() {
    int m, n;
    while (scanf("%d%d", &m, &n) != EOF) {   
        if (m == -1 && n == -1) {
           break;
        }
        for (int i = 0; i < n; ++i) {
            scanf("%lf%lf", &arr[i].weight, &arr[i].cost);
        }
        sort(arr, arr + n, Compare); //性价比降序排列
        double answer = 0;
        for (int i = 0; i < n; ++i) {
            if (m >= arr[i].cost) { //全部买下
                m -= arr[i].cost;
                answer += arr[i].weight;
            } else { //只能买部分
                answer += arr[i].weight * (m / arr[i].cost);
                break;
            }
        }
        printf("%.3f\n", answer);
    }
    return 0;
}