文章

27

粉丝

86

获赞

7

访问

15.7k

头像
喝饮料 题解:
P1478
发布于2023年8月18日 12:36
阅读数 522

C++

非常经典的贪心算法题 

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
struct water{
	double m;  // 毫升
	double w;  // 价格
};
bool cmp(water a, water b){
	return a.w / a.m < b.w / b.m;
}
int main(){
	int x, n;
	while(cin >> x >> n){
		if(x == -1 && n == -1){
			break;
		}
		vector<water> waters(n);
		vector<water>::iterator it;
		for(it = waters.begin(); it != waters.end(); it++){
			cin >> it->m >> it->w;
		}
		sort(waters.begin(), waters.end(), cmp);
		// for(it = waters.begin(); it != waters.end(); it++){
		// 	cout << it->m << it->w << endl;
		// }
		double sum = 0;
		for(int i = 0; i < n; i++){
			if(x - waters[i].w >= 0){
				sum += waters[i].m;
				x -= waters[i].w;
			}
			else{
				sum += (x / (waters[i].w / waters[i].m));
				break;
			}
		}
		cout << fixed << setp...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发