http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1007&cid=22619
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 37 24 35 220 325 1824 1515 10-1 -1
Sample Output
13.33331.500
Author
Source
ZJCPC2004
#include<iostream>
using namespace std; void app(double a[],double b[],double c[],int n) { int i,k,j; double t; for(i=0;i<n;i++) { k=i; for(j=i+1;j<n;j++) if(c[j]>c[k]) k=j; if(i!=k) { t=a[k]; a[k]=a[i]; a[i]=t; t=b[k]; b[k]=b[i]; b[i]=t; t=c[k]; c[k]=c[i]; c[i]=t; } } } int main() { int i,n,k; double a[1001],b[1001],c[1001],d,sx,m; while(scanf("%lf %d",&m,&n)==2) { if(m==-1&&n==-1) break; for(k=0;k<n;k++) { scanf("%lf",&a[k]); scanf("%lf",&b[k]); c[k]=a[k]/(1.0*b[k]); } app(a,b,c,n); sx=m; d=0; for(i=0;i<n;i++) { if(sx-b[i]>0) { d=d+a[i]; sx=sx-b[i]; } else { d=d+c[i]*sx; break; } if(sx==0) break; } printf("%.3f\n",d); } return 0; }