潍坊建公司网站,西部数码WordPress开启伪静态,2345游戏盒子,网页的制作公司【题目来源】https://www.lanqiao.cn/problems/3744/learning/【题目描述】 在小蓝的生日那天#xff0c;他得到了一个由神秘人赠送的拼图游戏#xff0c;每个拼图都有其特定的价值和相应的优惠券。小蓝决定要买下所有的拼图#xff0c;但他希望能尽可能地节省花费。小蓝手中…【题目来源】https://www.lanqiao.cn/problems/3744/learning/【题目描述】 在小蓝的生日那天他得到了一个由神秘人赠送的拼图游戏每个拼图都有其特定的价值和相应的优惠券。小蓝决定要买下所有的拼图但他希望能尽可能地节省花费。小蓝手中有 N 个拼图每个拼图的价格不同第 i 个拼图的价格为 Pi。同时他有 M 张优惠券每张优惠券都有其特定的使用条件只有当拼图的价格至少为 Li 时他才能使用这张优惠券并且可以享受 Di 的折扣。每张优惠券只能使用一次且同一件拼图不能同时使用多张优惠券。如果某件拼图没有使用优惠券则需要按照其标价购买。请你帮助小蓝计算出购买所有拼图所需的最少金额。【输入格式】 第一行输入两个整数 N 和 M分别表示拼图的数量和优惠券的数量。 接下来一行读入 N 个整数 P1P2…Pn表示每个拼图的价格。 接下来一行读入 M 个整数 L1L2…Lm表示每个优惠卷的使用门槛。 接下来一行读入 M 个整数 D1D2…Dm表示每个优惠卷的折扣。 数据范围保证1≤N, M≤2×10^51≤Pi≤10^91≤Di≤Li≤10^9。【输出格式】 输出一个整数表示购买所有拼图所需的最少金额。【输入样例】 2 5 12 8 5 11 5 11 10 3 9 1 3 2【输出样例】 8【算法分析】 ● 注意“同一件拼图不能同时使用多张优惠券”也要明确“优惠券使用后就不存在了”。 ● 本题使用大根堆priority_queueint,vectorint,lessint pq;【算法代码】
#include bits/stdc.h
using namespace std;const int maxn2e55;
int p[maxn];
pairint,int tkt[maxn];
priority_queueint,vectorint,lessint pq;
long long ans0;int main() {int n,m;cinnm;for(int i0; in; i) cinp[i];for(int i0; im; i) cintkt[i].first;for(int i0; im; i) cintkt[i].second;sort(p,pn); //small to bigsort(tkt,tktm); //small to bigint cnt0;for(int i0; in; i) {while(p[i]tkt[cnt].first cntm) {pq.push(tkt[cnt].second);cnt;}if(!pq.empty()) {ansp[i]-pq.top();pq.pop();} else ansp[i];}cout ans;return 0;
}/*
in1:
2 5
12 8
5 11 5 11 10
3 9 1 3 2out1:
8
------------
in2:
1 2
9
10 9
10 3out2:
6
*/【参考文献】https://www.lanqiao.cn/problems/3744/learning/
