文章

14

粉丝

132

获赞

7

访问

33.8k

头像
组队刷题 题解:贪心
P1307
发布于2024年2月1日 16:56
阅读数 646

#include <bits/stdc++.h>//万能头文件
using namespace std;
 
struct node{
	double w,m;
}p[1005];
 
bool cmp(node a,node b){
	return a.m/a.w <b.m/b.w;
} 
 
int main(){
	int x,n;
	while(scanf("%d%d",&x,&n) !=EOF){
		if(n==-1&&x==-1) break;
		for(int i = 1;i<=n;i++)
			scanf("%lf%lf",&p[i].w,&p[i].m);
			
		sort(p+1,p+n+1,cmp);
		double ans = 0;
		for(int i = 1;i<=n;i++){
			if(x>p[i].m){
				ans += p[i].w;
				x-=p[i].m;
			}
			else{
				ans += (p[i].w*x/p[i].m);
				break;
			}
		}
		printf("%.3lf\n",ans);
	}
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发