贪心

it2022-05-07  7

#include<stdio.h> #include<algorithm> using namespace std; #define M 1002 struct node { int j,f; }; struct node jf[M]; bool cmp(const node &a,const node &b) { return 1.0 * a.j / a.f > 1.0 * b.j / b.f; } int main() { // freopen("in.txt","r",stdin); int m,n; double s; while(scanf("%d%d",&m,&n) + m + n) { for(int i=0; i<n; i++) { scanf("%d%d",&jf[i].j,&jf[i].f); } sort(jf,jf + n,cmp); s = i = 0; while(m>0 && i<n) { if(m >= jf[i].f) s += jf[i].j; else s += 1.0 * m / jf[i].f * jf[i].j; m -= jf[i].f; i++; } printf("%.3lf\n",s); } return 0; }

 

转载于:https://www.cnblogs.com/lk1993/p/3258991.html


最新回复(0)