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

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

题目大意：

肥鼠准备了 M 磅的猫粮，准备和看管仓库的猫交易，仓库里装有他最喜爱的食物 Java 豆。

仓库有 N 个房间。第 i 间房包含了 J[i] 磅的 Java 豆，需要 F[i] 磅的猫粮。肥鼠不必为了房间中的所有 Java 豆而交易，相反，他可以支付 F[i] * a% 磅的猫粮去交换得到 J[i] * a% 磅的 Java 豆。这里，a 表示一个实数。

现在他将这项任务分配给了你：请告诉他，能够获得的 Java 豆的最大值是多少。

注意这个‘%’是百分之！！不是取模！！！傻子了吧、、、

解题报告：

  赤果果的贪心，，排序后先买最值得买的，直到钱花光了。

AC代码：

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define ll long long using namespace std; int n; double m,ans; struct Node {int j,f; } node[1005]; bool cmp(Node a,Node b) {return 1.0*a.j/a.f > 1.0*b.j/b.f; } int main() {while(cin>>m>>n) {if(n == -1 && m == -1) break;for(int i = 1; i<=n; i++) {scanf("%d%d",&node[i].j,&node[i].f);}ans=0;sort(node+1,node+n+1,cmp);for(int i = 1; i<=n; i++) {if(m >= node[i].f) {m-=node[i].f;ans+=node[i].j;}else {ans += (m/node[i].f)*node[i].j;break;}}printf("%.3lf\n",ans);}return 0 ;}

 

总结

以上是生活随笔为你收集整理的【HDU - 1009 】FatMouse' Trade （贪心）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。