刚开始题意没有理解,总算理解了,今天起床有点晚了,惩罚下自己,不吃饭了;饿着肚子写的水题;
题意:有n磅的cat food ,m个房间,第i个房间有J[i]磅JavaBean和F[i]磅cat food ,可以用a%的F[i],换取该房间的a%的J[i];
分析:按照每个房间J[i]/F[i]自大到小排序;
#include<cmath> #include<algorithm> #include<cstdio> using namespace std; #define lson l, mid, rt<<1 #define rson mid+1,r,rt<<1 | 1 const int N=1000; struct node { double J; double F; }a[N]; bool cmp(node a,node b) { return (a.J/a.F)>(b.J/b.F); } int main() { double n,m; while(~scanf("%lf%lf",&n,&m)) {if((int)n==-1&&(int)m==-1)break; for(int i=0;i<(int)m;i++) { scanf("%lf%lf",&a[i].J,&a[i].F); } sort(a,a+(int)m,cmp); double sum=0; for(int i=0;i<(int)m;i++) { if(a[i].F<n) { n=n-a[i].F; sum = sum+a[i].J; } else if(a[i].F==n){ sum=sum+a[i].J;break; } else if(a[i].F>n) { sum =sum+ a[i].J*(n/a[i].F);break; } } printf("%.3lf\n",sum); } return 0; }