hdu 1009 FatMouse'Trade （贪心算法）
FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.
The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.
胖老鼠准备了M磅的猫粮，准备与守卫（包含他最喜欢的食物JavaBean）的仓库的猫交易。仓库有N个房间。第i个房间包含J [i]磅的JavaBeans并且需要F [i]磅的猫粮。胖老鼠不需要与房间里的所有JavaBeans进行交易，而是，如果他支付F [i] *a％磅的猫粮，他可能会得到J[i]* a% 磅的JavaBeans。这是一个实数。现在他正在为你分配这个任务：告诉他，他可以获得的最大JavaBeans数量。
输入：The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1's. All integers are not greater than 1000.
输入包含多个测试用例。每个测试用例以包含两个非负整数M和N的行开始。然后是N行，每行包含两个非负整数J [i]和F [i]。最后一个测试用例后跟两个-1。所有整数不大于1000。
输出：For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.
对于每个测试用例，在一行中打印一个实数，最多精确到3个小数位，这是FatMouse可以获得的最大JavaBeans数量。
解题思路：既然每个房间的JavaBean和所需要的猫粮可能不一致，即JavaBean/猫粮的比例不一致，比例越大，表示可以花费少量的猫粮获取更多的JavaBean。所以我们可以通过将每个房间的 JavaBean/猫粮 按照从大到小的排序，然后根据所拥有的猫粮数量来依次换取JavaBean。如果房间里的JavaBean/猫粮 比例相同，那么我们应该选取相同比例下能获取到的JavaBean更多的房间，如此便能获得最多的JavaBean。
样例输入：5 3 拥有5磅猫粮 3个房间
7 2 房间1需要2榜猫粮 获取7磅JavaBean 7/2 = 3.5
4 3 房间2需要3榜猫粮 获取4磅JavaBean 4/3 = 1.33...
5 2 房间3需要2榜猫粮 获取5磅JavaBean 5/2 = 2.5
根据比例房间排序应该是132，因此先用2磅猫粮换取房间1的7磅的JavaBean，然后再用2磅的猫粮换取3号房间的5磅JavaBean。最后剩到1磅的猫粮换取2号房间的 1*4/3 = 1.333 的JavaBean。
因此总的输出是 7+5+1.333 = 13.333
AC 代码如下 运行时间124MS 运行内存 1896K#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct Mouse
{
double j;//JavaBean
double f;//猫粮
double a;//j/f的比例值
};
bool Comp(const Mouse &d1, const Mouse &d2)
{
if (d1.a != d2.a) //比例不同 返回比例大的
return d1.a > d2.a;
else //比例相同 返回需要猫粮更少的
return d1.f < d2.f;
}
int main()
{
int m, n, i;
vector<Mouse>v;
Mouse mouse;
cout.precision(3);//输出精确到 3 个小数位
double sum;//记录总量
while (cin >> m >> n)
{
if (m == -1 && n == -1)//循环出口
break;
v.clear();
sum=0.0;
for (i = 0; i < n; i++)//依次输入房间参数
{
cin >> mouse.j >> mouse. f;
mouse.a = mouse.j/ mouse.f; //JabaBean与猫粮比例
v.push_back(mouse);
}
sort(v.begin(), v.end(), Comp); //从小到大排序
for (i = 0; i < v.size(); i++) //依次查询房间
{
if (m >= v[i].f) //猫粮充足则交换
{
sum = sum + v[i].j;
m = m - v[i].f;
}
else //猫粮不充足，则按照比例交换
{
sum = sum + m*v[i].a;
break;
}
}
cout << fixed << sum << endl; //注意输出精度精确到3位小数
}
return 0;
}
相关知识
hdu 1009 FatMouse'Trade （贪心算法）
贪心之老鼠与猫的交易（详细分析）
德国纽伦堡国际宠物用品展览会International Trade Fair for Pet Supplies
猫咪免费领养套路❗️别被贪心蒙了眼
随机化算法(1) — 随机数
蚁群算法+Dijkstra算法=二维路径规划,基于蚁群算法的机器人路径规划,matlab源码.rar资源
ABC英语角宠物助手算法
ID3算法（含实例）
粒子群算法学习(PSO)
动物语音识别用什么算法
网址: hdu 1009 FatMouse'Trade （贪心算法） https://m.mcbbbk.com/newsview349870.html
| 上一篇: 按美国NIH |
下一篇: 百年汪曾祺留给孩子的礼物 |
