解题思考G. 老鼠和猫的交易
题目描述
Problem Description
小老鼠准备了M磅的猫粮，准备去和看守仓库的猫做交易，因为仓库里有小老鼠喜欢吃的五香豆。
仓库有N个房间；
第i个房间有J[i] 磅的五香豆，并且需要用F[i]磅的猫粮去交换；
老鼠不必交换该房间所有的五香豆，换句话说，它可以用 F[i] a% 磅的猫粮去换取J[i] a%磅的五香豆，其中a是一个实数。
现在，请帮忙计算一下，小老鼠最多能够得到多少磅的五香豆？
Input
输入包含多组测试用例。
每组测试数据首先一行是2个非负整数M和N，接着的N行，每行分别包含2个非负整数J[i]和F[i]。
输入数据以两个-1结束。
题目保证所有的数据不超过1000.
Output
请计算并输出小老鼠最多能够得到的五香豆数量。
每组数据输出一行，保留3位小数。
输入样例
5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1
输出样例
13.333
31.500
思考：贪心算法，先取完性价比高的房间，四舍五入算法在结尾需特殊注意，也是选取此题的原因
#include<bits/stdc++.h>
usingnamespacestd;
structcat{
doublea,b;
doublec;
}arr[1000];
boolcmp(catx,caty)
{
returnx.c>y.c;
}
intmain()
{
intm,n;
while(cin>>m>>n)
{
doublecount=0;
if(m==-1&&n==-1)
break;
for(inti=0;i<n;i++)
cin>>arr[i].a>>arr[i].b;
for(inti=0;i<n;i++)
arr[i].c=arr[i].a/arr[i].b;
sort(arr,arr+n,cmp);
for(inti=0;i<n;i++)
{
if(m<arr[i].b)
{
count=count+(m/arr[i].b)*arr[i].a;
break;
}
else
count=count+arr[i].a;
m=m-arr[i].b;
if(m-0<0.0001)
break;
}
//count=(int)(count*10000+0.5)/10000.0;
count*=1000;
count=(int)(count+0.5);
count/=1000;
printf("%.3fn",count);
}
return0;
}
/*测试排序功能 插入sort函数后 for(inti=0;i<n;i++)
{
cout<<arr[i].a<<endl;
}*/
相关知识
问题 G: 老鼠和猫的交易
宠物叫声扰民引发邻里矛盾，济南这个派出所解题有“窍门”
2023年的国考：申论备考干货综合分析的之解题思路
交易猫安全吗
想做宠物的老鼠
抓老鼠的猫品种
怎么看猫会不会抓老鼠 怎样看猫会不会捉老鼠
猫抓老鼠的秘密，宠物猫为啥不会抓老鼠？猫：我妈没教！
猫抓老鼠，老鼠胜！猫的奇怪行为
老鼠的个性，智力和关怀
网址: 解题思考G. 老鼠和猫的交易 https://m.mcbbbk.com/newsview349865.html
| 上一篇: 来到老鼠窟窿藏粮算找到地方了 |
下一篇: 按美国营养学会AIN |
