题解 | #FatMouse'Trade# 机试指南 贪心

//2023-4-16 简单的贪心算法  FatMouse's Trade
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1000;
//把咖啡豆当做商品,目标可以看成，用已有的M￥去买最多重量的咖啡豆，把N个房间看作N种咖啡豆商品的种类
//将咖啡豆的性价比按从高到低排序 先买最高性价比的咖啡豆，再依次顺延。此处的  性价比=cost/weight  用最少的钱买最多的咖啡豆
struct Bean
{
    double cost;//咖啡豆的花费
    double weight;//咖啡豆的重量
}bean[MAXN];
//自定义排序函数，将性价比从高到低排序

bool compare(Bean x,Bean y)
{
    return x.cost/x.weight < y.cost/y.weight;
}

int main()
{
    int m,n;
    //有多组输入 需要判断
    while(scanf("%d %d",&m,&n)!=EOF)
    {
        //题中说，如果-1 -1 则停止输入
        if(m==-1&&n==-1)
            break;
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&bean[i].weight,&bean[i].cost);
        }//输入结束，接下来对性价比排序
        sort(bean,bean+n,compare);//compare是自己定义的排序函数
        double answer=0;//最后买到的总咖啡豆的重量
        for(int i=0;i<n;i++)

        {
            if(m>=bean[i].cost)//可以买得起该房间内所有的咖啡豆
            {
                m-=bean[i].cost;
                answer+=bean[i].weight;
            }else{
                answer+=(m/bean[i].cost)*bean[i].weight;
                //m=0;
                break;//把M花完了
            }
        }
        printf("%.3f\n",answer);
    }
    return 0;
}