上海网站建设推广/流量主广告点击自助平台

【题目来源】
https://www.lanqiao.cn/problems/3744/learning/

【题目描述】
在小蓝的生日那天，他得到了一个由神秘人赠送的拼图游戏，每个拼图都有其特定的价值和相应的优惠券。小蓝决定要买下所有的拼图，但他希望能尽可能地节省花费。小蓝手中有 N 个拼图，每个拼图的价格不同，第 i 个拼图的价格为 Pi。同时，他有 M 张优惠券，每张优惠券都有其特定的使用条件：只有当拼图的价格至少为 Li 时，他才能使用这张优惠券，并且可以享受 Di 的折扣。每张优惠券只能使用一次，且同一件拼图不能同时使用多张优惠券。如果某件拼图没有使用优惠券，则需要按照其标价购买。请你帮助小蓝计算出购买所有拼图所需的最少金额。

【输入格式】
第一行输入两个整数 N 和 M，分别表示拼图的数量和优惠券的数量。
接下来一行读入 N 个整数 P1，P2，…，Pn，表示每个拼图的价格。
接下来一行读入 M 个整数 L1，L2，…，Lm，表示每个优惠卷的使用门槛。
接下来一行读入 M 个整数 D1，D2，…，Dm，表示每个优惠卷的折扣。
数据范围保证：1≤N, M≤2×10^5，1≤Pi≤10^9，1≤Di≤Li≤10^9。

【输出格式】
输出一个整数，表示购买所有拼图所需的最少金额。

【输入样例】
2 5
12 8
5 11 5 11 10
3 9 1 3 2

【输出样例】
8

【算法分析】
● 注意“同一件拼图不能同时使用多张优惠券”，也要明确“优惠券使用后就不存在了”。
● 本题使用大根堆：priority_queue<int,vector<int>,less<int>> pq;

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int maxn=2e5+5;
int p[maxn];
pair<int,int> tkt[maxn];
priority_queue<int,vector<int>,less<int>> pq;
long long ans=0;int main() {int n,m;cin>>n>>m;for(int i=0; i<n; i++) cin>>p[i];for(int i=0; i<m; i++) cin>>tkt[i].first;for(int i=0; i<m; i++) cin>>tkt[i].second;sort(p,p+n); //small to bigsort(tkt,tkt+m); //small to bigint cnt=0;for(int i=0; i<n; i++) {while(p[i]>=tkt[cnt].first && cnt<m) {pq.push(tkt[cnt].second);cnt++;}if(!pq.empty()) {ans+=p[i]-pq.top();pq.pop();} else ans+=p[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/