PAT 7

PAT 7

本题考点：

• 优先队列的使用

在火星上有个魔法商店，提供魔法优惠券。每个优惠劵上印有一个整数面值K，表示若你在购买某商品时使用这张优惠劵，可以得到K倍该商品价值的回报！该商店还免费赠送一些有价值的商品，但是如果你在领取免费赠品的时候使用面值为正的优惠劵，则必须倒贴给商店K倍该商品价值的金额…… 但是不要紧，还有面值为负的优惠劵可以用！（真是神奇的火星）
例如，给定一组优惠劵，面值分别为1、2、4、-1；对应一组商品，价值为火星币M$7、6、-2、-3，其中负的价值表示该商品是免费赠品。我们可以将优惠劵3用在商品1上，得到M$28的回报；优惠劵2用在商品2上，得到M$12的回报；优惠劵4用在商品4上，得到M$3的回报。但是如果一不小心把优惠劵3用在商品4上，你必须倒贴给商店M$12。同样，当你一不小心把优惠劵4用在商品1上，你必须倒贴给商店M$7。
规定每张优惠券和每件商品都只能最多被使用一次，求你可以得到的最大回报。

本题是优先队列的使用经典案例，我们将正数和负数分开存放，正数放到大顶堆中，负数放到小顶堆中，然后分别从两个堆中去除对应的值相乘然后相加即可获得最大值。

完整代码如下：

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;priority_queue<int> posiGoods, posiDiscounts;   // 正数采用大顶堆
priority_queue<int, vector<int>, greater<int>> negaGoods, negaDiscounts;    // 负数采用小顶堆int main()
{int n, temp;scanf("%d", &n);for (int i = 0; i < n; i++){scanf("%d", &temp);if (temp > 0)posiGoods.push(temp);elsenegaGoods.push(temp);}scanf("%d", &n);for (int i = 0; i < n; i++){scanf("%d", &temp);if (temp > 0)posiDiscounts.push(temp);elsenegaDiscounts.push(temp);}int sum = 0;while (!pty() && !pty()){sum += p() * p();posiDiscounts.pop();posiGoods.pop();}while (!pty() && !pty()){sum += p() * p();negaGoods.pop();negaDiscounts.pop();}printf("%d", sum);return 0;
}