FatMouse' Trade

发布时间:2014-10-22 19:59:47编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"FatMouse' Trade",主要涉及到FatMouse' Trade方面的内容,对于FatMouse' Trade感兴趣的同学可以参考一下。

题目连接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=40692#problem/A 描述 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 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1  样例输出 13.333 31.500  贪心思路:先交换性价比大的,在交换性价比 #include<stdio.h> #include<algorithm> using namespace std; struct mouse { double j,f; double cent; }a[1100]; bool cmp(mouse x,mouse y) { return (x.cent>y.cent); } int main() { int n,m,i; double sum; while(scanf("%d %d",&m,&n)!=EOF) { sum=0; if(m==-1 && n==-1) break; else { for(i=0;i<n;i++) { scanf("%lf %lf",&a[i].j,&a[i].f); a[i].cent=a[i].j/a[i].f; } sort(a,a+n,cmp); for(i=0;i<n;i++) { if(a[i].f<=m) { sum=sum+a[i].j; m=m-a[i].f; } else { sum=sum+a[i].cent*m; break; } } } printf("%.3f\n",sum); } return 0; }



关键词: FatMouse' Trade