问题描述
FatMouse准备了M磅的猫粮，准备与守卫仓库的猫交易，里面装着他最喜欢的食物JavaBean。
仓库有N个房间。i-th 房间包含 J [i] 磅爪哇豆， 需要一磅猫粮。FatMouse不必用房间里所有的爪哇豆来交换，相反，如果他付给F[i]1%磅的猫粮，他可能会得到J[i]1%磅的爪哇豆。这里有一个真实的数字。现在，他正在给你分配这个作业：告诉他能得到的最大数量的爪哇豆。
输入
输入由多个测试案例组成。每个测试案例以包含两个非阴性整数 M 和 N 的行开头。然后N行跟随，每个线分别包含两个非负整数J[i]和F[i]。最后一个测试案例后面是两个-1的。所有整数不超过 1000。
输出
对于每个测试案例，在一行中打印一个精确到 3 个小数位的真实数字，这是 FatMouse 可以获得的最大爪哇豆量。
示例输入
5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1
样本输出
13.333
31.500
代码实现：（可AC）
#include <stdio.h> #include <algorithm>//sort函数排序头文件 using namespace std;//避免发生命名冲突 const int W=1e4+5; int M, N;//猫粮数 房间数 double tot = 0;//换取的奶酪数 struct room{ double cat_food; double cheese; }a[W];//数组要开得足够大 ，数组小的话不能AC，第一次的时候会显示超时 bool cmp(room x, room y) { return (x.cheese) / x.cat_food > (y.cheese) / y.cat_food;//题中说明一定比例的猫粮可以换到一定比例的奶酪，贪心算法找性价比最高的 }//sort函数部分，从大到小排序 int main() { while(scanf("%d %d", &M, &N)!=EOF)//EOF处理多组数据 ，M代表猫粮，N代表房间个数 { if(M==-1&&N==-1)break;//题中说明 输入-1 -1 时停止输入 for(int i = 1; i <= N; i ++) { scanf("%lf %lf", &a[i].cheese, &a[i].cat_food);//读入猫粮和 } sort(a + 1, a + 1 + N, cmp);//使用sort函数时，要注意第一个值的位置 for(int i = 1; i <= N; i ++) { if(M-a[i].cat_food>=0){//如果老鼠所持有的猫粮大于一只猫所需的猫粮 tot+=1.0*a[i].cheese*1.0;//奶酪不断累积 M-=a[i].cat_food;//猫粮不断减少 } else{//若老鼠手中的猫粮不足以购买这间房子里面的所有奶酪 按比例进行获取 tot+=1.0*a[i].cheese/a[i].cat_food*M; break; } } printf("%.3lf\n", tot); tot = 0;//恢复现场 } return 0; }
/
注意：
List item
当老鼠的猫粮不足以支付整间房屋的奶酪时，可以按照一定的比例进行换取
List item
排序时使用sort函数
List item
恢复现场
List item
-1 -1 的判断
List item
奶酪做比例时，可以使用double ，如果是int类型，结果会出错
List item
关于交换问题，可以在纸上进行推演
参考：
参考博文
