王道机试指南 例题7.2 FatMouse's Trade

题目：

题目大意：

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

struct st{
    double price;//每个仓库咖啡豆的单价
    int seq;//记录仓库号
};

bool compare(st x,st y){
    return x.price<y.price;
}

int main(){
    int m,n;
    while(cin>>m>>n && (m!=-1 && n!=-1)){
        int j[n],f[n];
        for(int i=0;i<n;i++){
            cin>>j[i]>>f[i];
        }
        st s[n];
        for(int i=0;i<n;i++){
            s[i].price=(f[i]*1.0)/j[i];
            s[i].seq=i;
        }
        sort(s,s+n,compare);//按单价排序
        int i=0;
        double totalBean=0;
        while(m>0){//按单价从低到高购买咖啡豆，直到猫粮耗尽
            int seq=s[i].seq;
            if(m>f[seq]){//剩余猫粮可以购买当前仓库的所有咖啡豆
                totalBean+=j[seq];
                m-=f[seq];
                i++;
            }
            else{//剩余猫粮不够购买当前仓库的所有咖啡豆
                totalBean+=((m*1.0)/f[seq])*j[seq];
                m=0;
            }
        }
        printf("%5.3f\n",totalBean);
    }
    return 0;
}

运行结果：