FatMouse

题目描述：

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. 

输入：

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.

输出：

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.

样例输入：

5 37 24 35 220 325 1824 1515 10-1 -1

样例输出：

13.33331.500

Code:

#include <cstdio>#include <algorithm> using namespace std; struct goods{    double weight;        //该物品总重    double totalValue;    //该物品总价值    double price;         //该物品性价比}; bool cmp(goods a,goods b){    return a.price>=b.price;} int main(){    double n;   //一共多少钱    const int arrSize=1010;    int m;      //有几样物品    goods arr[arrSize];    while(scanf("%lf%d",&n,&m)!=EOF){        if(n==-1&&m==-1)            break;        for(int cnt=0;cnt<m;++cnt){            scanf("%lf%lf",&arr[cnt].weight,&arr[cnt].totalValue);            arr[cnt].price=arr[cnt].weight/arr[cnt].totalValue;        }        sort(arr,arr+m,cmp);        double ans=0;        int index=0;        while(n>0&&index<m){            if(n>arr[index].totalValue){   //若能买下全部该商品                ans+=arr[index].weight;                n-=arr[index].totalValue;            }else{                ans+=n/arr[index].totalValue*arr[index].weight;                n=0;            }            ++index;        }        printf("%.3lf\n",ans);    }    return 0;} /**************************************************************    Problem: 1433    User: lcyvino    Language: C++    Result: Accepted    Time:10 ms    Memory:1020 kb****************************************************************/

 

关于【贪心算法】