首页 > 代码库 > Hdu 1009 FatMouse' Trade

Hdu 1009 FatMouse' Trade

2024-07-17 00:26:49   224人阅读

FatMouse‘ Trade

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 43156    Accepted Submission(s): 14417


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
 

 

Author
CHEN, Yue
 

 

Source
ZJCPC2004
 

 

Recommend
JGShining
 
 
贪心.
贪心策略是根据价值比进行降序排序 ：J[i]/F[i];
代码如下：
 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 #define MAX 1001 7 struct node 8 { 9     int f;10     int j;11     double p;12 };13 struct node x[MAX];14 int n,m;15 bool cmp(struct node x,struct node y)16 {17     if(x.p==y.p) return x.f<y.f;18     return x.p>y.p;19 }20 void out()21 {22     for(int i=0;i<n;i++)23         cout<<x[i].p<<" ";24     cout<<endl;25 }26 void init()27 {28     memset(x,0,sizeof(x));29 }30 void read()31 {32     int i;33     for(i=0;i<n;i++)34     {35         scanf("%d %d",&x[i].j,&x[i].f);36         x[i].p=(double)(x[i].j*1.0/(x[i].f*1.0));37     }38     sort(x,x+n,cmp);39 }40 void cal()41 {42     int i;43     double res=m;44     double ans=0;45     for(i=0;i<n;i++)46     {47         if(res>=x[i].f)48         {49             res-=x[i].f;50             ans+=x[i].j;51         }52         else53         {54             ans=ans+res*x[i].p;55             res-=res;56         }57     }58     printf("%.3f\n",ans);59 }60 void solve()61 {62     init();63     read();64     cal();65 }66 67 int main()68 {69     while(scanf("%d %d",&m,&n)!=EOF)70     {71         if(n==-1&&m==-1) break;72         solve();73     }74     return 0;75 }

 

 


联系
我们