文章

10

粉丝

0

获赞

18

访问

546

头像
喝饮料 题解:贪心
P1478 云南大学机试题
发布于2026年2月20日 20:13
阅读数 77

#include <vector>
#include <queue>
#include <string>
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;
struct drink
{
	float m;
	float w;
	float av;
};
bool cmp(drink a,drink b)
{
	return a.av>b.av;
}
int main()
{

	float x;
	int n;
	while(cin>>x>>n&&(x!=-1&&n!=-1)){
	vector<drink> v;
	float mi,wi;
	for(int i=0;i<n;i++)
	{
		cin>>mi>>wi;
		drink d;
		d.m=mi;
		d.w=wi;
		d.av=mi/wi;//每元能买多少饮料
		v.push_back(d);
	}
	sort(v.begin(),v.end(),cmp);
	float sum=0,total=0;
	for(int i=0;i<n;i++)
	{
		if(sum+v[i].w<=x)
		{
			sum=sum+v[i].w;
			total=total+v[i].m;
		}
		else
		{
			total+=(x-sum)*v[i].av;
			break;
		}
	}
	printf("%.3f\n",total);
	}
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发