【可撤销贪心 堆】SSL_1148 购物

本文主要是介绍【可撤销贪心 堆】SSL_1148 购物，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出$N$件商品，$K$张优惠券，每个商品原价为$p_i$，使用优惠券后价格为$q_i$，现在有$M$钱，求出最多能买多少件商品。

思路

开$3$个小根堆，分别放$p_i$，$q_i$，$p_i-q_i$，其中$p_i-q_i$相当于再花那么多钱就可以得到一张优惠券（可撤销）。每次我们比较一下是直接买优惠还是买优惠券再买优惠。

代码

#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;struct node{int num, id;
};
bool operator < (node x, node y) {return x.num > y.num;
}
priority_queue<node> q1, q2;
priority_queue<int, vector<int>, greater<int> > q3;
int N, K, ans;
long long M;
int use[150001], p[150001], q[150001];int main() {scanf("%d %d %lld", &N, &K, &M);for (int i = 1; i <= N; i++) {scanf("%d %d", &p[i], &q[i]);q1.push((node){p[i], i});q2.push((node){q[i], i});}for (int i = 1; i <= K; i++) q3.push(0);//一开始有k张优惠券for (; M > 0 && ans < N; ans++) {while (use[q1.top().id]) q1.pop();while (use[q2.top().id]) q2.pop();if (q1.top().num <= q2.top().num + q3.top()) {//直接买node x = q1.top();M -= x.num;if (M < 0) break;use[x.id] = 1;q1.pop();}else {//花券买node x = q2.top();M -= x.num + q3.top();if (M < 0) break;use[x.id] = 1;q3.pop();q3.push(p[x.id] - q[x.id]);//新放入这个物品可撤回的优惠券q2.pop();}}printf("%d", ans);
}

这篇关于【可撤销贪心 堆】SSL_1148 购物的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---