HDU-1009.FatMouse‘Trade

题意

这是需要用M磅猫粮去和猫兑换仓库中的JavaBean，每个仓库中的JavaBean数量和价格不完全一致，如何才能兑换到更多的JavaBean
这里有一句大致意思是：不要买完仓库中的全部

思路

这是一个简答贪心问题，我只需要每次购买当前剩余产品中性价比最高的产品即可
如果能全换完，那就换完，否则兑换等比例JavaBean

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=1000;
struct JavaBean{double weight;double cost;
}; JavaBean a[MAXN]; bool cmp(JavaBean x,JavaBean y)
{return x.weight/x.cost>y.weight/y.cost;
}int main(void)
{int n,m;while(scanf("%d %d",&n,&m) != EOF){if(n==-1 && m==-1)break;for(int i=0;i<m;++i){scanf("%lf %lf",&a[i].weight,&a[i].cost);}sort(a,a+m,cmp); //将权值大的放在前面，最先兑换，权值小的放在后边 double answer=0;for(int i=0;i<m;++i){if(n>=a[i].cost){n-=a[i].cost;answer+=a[i].weight;}else//如果不能全部兑换，则兑换部分，因为这个题可以不全部买完 {answer +=a[i].weight *(n/a[i].cost);n=0;break;}}printf("%.3lf\n",answer);}return 0;
}