杭电1009 FatMouse's Trade

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

 

题目大意：

一只肥鼠一开始有M个猫粮，经过N个房间。在每个房间，它可以用F[i]*a%的猫粮去换取J[i]*a%的鼠粮。

由于物品可分割，不能使用背包。

 

直接贪心，用结构体构造，按照Rate = f / j 这样的最大比例去排序，依次拾取即可。

 

AC代码：

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <cmath>
#include <stack>
#include <stdlib.h>
//#define DEBUG
using namespace std;
typedef long long ll;
double m;
int n;
struct p{
    double j;
    double f;
    double rate;
}pp[1005];
bool cmp(p a,p b) { //结构体构造排序
    if(a.rate==b.rate) return a.f<=b.f;
    return a.rate>b.rate;
}
int main() {
    while(cin>>m>>n) {
        if(m==-1&&n==-1) return 0;
        memset(pp,0, sizeof(pp));
        for(int i=0;i<n;i++) {
            cin>>pp[i].j>>pp[i].f;
            pp[i].rate=pp[i].j/pp[i].f;
        }
        sort(pp,pp+n,cmp);
        double sum=0;
        for(int i=0;i<n;i++) {
            if(m>=pp[i].f) {    //整取
                sum+=pp[i].j;
                m-=pp[i].f;
            }
            else if(m>0&&m<pp[i].f) {  //分取
                sum+=pp[i].j* (m/pp[i].f);
                break;
            }
        }
        printf("%.3lf\n",sum);
    }
    return 0;
}