PAT-Advanced Greedy

Abstract：贪心相关，感觉都比较浅

1037 Magic Coupon (25分)

解法一：就硬排序

首先目标一是要赚钱，第二是要赚尽可能多的钱，所以我们的原则是

• 不干亏钱的买卖
• 用最大的正优惠券买价值最大的商品，用最小的负优惠券买最小的负价商品

因此读入数据的时候就把优惠券和商品正负分开读入，其次正价组降序，负价组升序，然后遍历计算最大利润就行

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

int n, m, c, p, sum = 0;
std::vector<int> c1, p1, c2, p2;

void parseInput() {
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		std::cin >> c;
		if (c > 0)
			c1.push_back(c);
		else
			c2.push_back(c);
	}

	std::cin >> m;
	for (int i = 0; i < m; i++) {
		std::cin >> p;
		if (p > 0)
			p1.push_back(p);
		else
			p2.push_back(p);
	}
}

int greater(int a, int b) {
	return a > b;
}

int main() {
	parseInput();
	std::sort(c1.begin(), c1.end(), greater);
	std::sort(p1.begin(), p1.end(), greater);
	std::sort(c2.begin(), c2.end());
	std::sort(p2.begin(), p2.end());
	for (int i = 0; i < c1.size(); i++) {
		if (i < p1.size()) sum += c1[i] * p1[i];
	}
	for (int i = 0; i < c2.size(); i++) {
		if (i < p2.size()) sum += c2[i] * p2[i];
	}
	std::cout << sum;

}