PAT-BASIC1020——月饼/PAT-ADVANCED1070——Mooncake

我的PAT-BASIC代码仓：https://github.com/617076674/PAT-BASIC

我的PAT-ADVANCED代码仓：https://github.com/617076674/PAT-ADVANCED

原题链接：

PAT-BASIC1020:https://pintia.cn/problem-sets/994805260223102976/problems/994805301562163200

PAT-ADVANCED1070:https://pintia.cn/problem-sets/994805342720868352/problems/994805399578853376

题目描述：

PAT-BASIC1020:

PAT-ADVANCED1070:

知识点：贪心算法

思路：优先售卖单价最高的商品

很明显的贪心算法。

时间复杂度是O(nlogn)，其中n为月饼种类数。空间复杂度为O(n)。

C++代码：

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct product {
	double quantity;
	double price;
};

bool compare(product product1, product product2);

int main() {
	int type;
	int need;

	cin >> type >> need;

	double quantity;
	double price;

	vector<double> quantities;
	vector<double> prices;
	vector<product> products;

	product moonCake;

	for (int i = 0; i < type; i++) {
		cin >> quantity;
		quantities.push_back(quantity);
	}
	for (int i = 0; i < type; i++) {
		cin >> price;
		prices.push_back(price);
	}
	for (int i = 0; i < type; i++) {
		moonCake.quantity = quantities[i];
		moonCake.price = prices[i];
		products.push_back(moonCake);
	}
	sort(products.begin(), products.end(), compare);
	double total = 0;
	double profit = 0;
	for (int i = 0; i < products.size(); i++) {
		if (total + products[i].quantity <= need) {
			profit += products[i].price;
			total += products[i].quantity;
		} else {
			profit += (need - total) * products[i].price / products[i].quantity;
			break;
		}
	}
	printf("%.2f", profit);
}

bool compare(product product1, product product2) {
	if (product1.price / product1.quantity - product2.price / product2.quantity >= 0) {
		return true;
	} else {
		return false;
	}
}

C++解题报告：