lanqiaoOJ 3744：小蓝的智慧拼图购物 ← pair+优先队列

【题目来源】
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 big
    sort(tkt,tkt+m); //small to big

    int 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 2

out1:
8
------------
in2:
1 2
9
10 9
10 3

out2:
6
*/

【参考文献】
https://www.lanqiao.cn/problems/3744/learning/