FatMouse的交易問題，FatMouse交易問題

FatMouse的交易問題，FatMouse交易問題

想按照某個值排序，用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;
}