hdoj1009-贪心

发表于 | 分类于

题目描述

Problem Description

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 trade for 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.

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

1
2
3
4
5
6
7
8
9
5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1

Sample Output

1
2
13.333
31.500

思路分析

题目不难，使用贪心解决即可。但最关键的是，如何找到一个合适的贪心策略。比如这里，最合适的当然是能够找到用更少的钱买到更多的食物，因此还需要计算物品的性价比。再将性价比降序排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

struct goods{
    double j; //该物品总重
    double f; //该物品总价值
    double s; //该物品性价比
    bool operator <(const goods &A) const{
        return s > A.s;
    }
}buf[1000];

int main(){
    double m; //总钱数
    int n;    //n种物品
    while(scanf("%lf%d", &m, &n) != EOF){
        if(m == -1 && n == -1) break;
        for(int i=0; i<n; i++){
            scanf("%lf%lf", &buf[i].j, &buf[i].f);
            buf[i].s = buf[i].j / buf[i].f; //计算性价比
        }
        sort(buf, buf+n); //性价比降序排序，贪心算法
        int idx = 0;
        double ans = 0;
        while(m > 0 && idx < n){
            if(m >= buf[idx].f){
                ans += buf[idx].j;
                m -= buf[idx].f;
            }
            else{
                ans += m*buf[idx].s;
                m = 0;
            }
            idx++;
        }
        printf("%.3f\n",ans);
    }
}