FatMouse的交易问题

时间:2023-12-17 15:39:20

想按照某个值排序,用sort()函数,结果想了半天不知道用数组怎么解决,然后看了答案,才知道原来可以用struct,想想我真是笨死了。。

原题描述以及答案如下:

Problem Description
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.



Input
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.



Output
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.



Sample Input
5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1



Sample Output
13.333 31.500


思路:题意就是给定猫食总量,然后去和猫换JavaBean,每个房间都有一定的JavaBean,每个房间换JavaBean需要的猫食不同。求利用有限的猫食,换取的最多的JavaBean是多少。
注意问题:1.考虑情况要全,比如刚开始就没有考虑foodNeed为0的情况
                  2.当涉及到浮点数运算时要用double,第一次用float没有通过,全部改成double就通过了。

/*Run ID Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language Author
*5849123 2012-04-26 12:44:02 Accepted 1009 78MS 364K 1148 B C++ JackieHowe
*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct Room
{
int foodHas;
int foodNeed;
double Proportion;
};

bool CompAccordPortion(Room r1,Room r2)
{
if(r1.Proportion==r2.Proportion)
return r1.foodHas>r2.foodHas;
return r1.Proportion>r2.Proportion;
}

int main()
{
int sumFood,numRoom;
while(cin>>sumFood>>numRoom && (sumFood!=-1 || numRoom!=-1))
{
vector<Room> vecRoom;
Room room;
int foodNow=0;
double amount=0;
for(int i=0;i<numRoom;i++)
{
cin>>room.foodHas>>room.foodNeed;
if(room.foodNeed==0)
{
room.Proportion=10000;
}
else
{
room.Proportion=(double)room.foodHas/(double)room.foodNeed;
}
vecRoom.push_back(room);
}
sort(vecRoom.begin(),vecRoom.end(),CompAccordPortion);
for(int i=0;i<vecRoom.size();i++)
{
if((vecRoom[i].foodNeed+foodNow)<=sumFood)
{
amount+=vecRoom[i].foodHas;
foodNow+=vecRoom[i].foodNeed;
}
else
{
amount+=vecRoom[i].Proportion*(double)(sumFood-foodNow);
break;
}
}
cout.precision(3);
cout<<fixed<<amount<<endl;
}
return 0;
}