题目大意

有 $N$ 个要买的商品，第 $i$ 个商品的原价是 $P_i$。

有 $M$ 张优惠券，第 $i$ 张优惠券需要满 $L_i$ 减 $D_i$。

一个物品最多只能使用一张优惠券，每一张优惠券最多使用一次。

问最小花费。

思路

首先因为每一个物品都必须买，所以问题就转化成了如何让这个总价格降价最多。

考虑贪心。

因为每一个物品最多只能使用一张优惠券，所以肯定要先用 $D$ 最大的。在 $D$ 相同时先用 $L$ 小的。因为 $L$ 小的能用的券就少。所以能给后面更大范围的更多机会。

之后我们把 $P$ 按照价格从小到大排一个序。之后从第一个优惠券开始向后枚举。二分价格最小的能用的 $P$。然后只要能用就将所有 $P$ 的总和减去当前的 $L$。

还有一个要注意的点是一个物品最多只能使用一张优惠券，所以在用完一张券的时候就要把对应的物品删除掉。

代码

#include <iostream>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const ll MAXN=2e5+5;
ll n,m;
struct node{
    ll l,d;
    bool operator<(const node&K)const{
        if(d!=K.d){
            return d>K.d;
        }
        return l<K.l;
    }
}c[MAXN];
ll ans;
map<ll,ll>ma;
int main() {
    scanf("%lld%lld",&n,&m);
    set<ll>p;
    for (int i = 1; i <=n ; ++i) {
        ll P;
        scanf("%lld",&P);
        ma[P]++;
        ans+=P;
        p.insert(P);
    }
    for (int i = 1; i <=m ; ++i) {
        scanf("%lld",&c[i].l);
    }
    for (int i = 1; i <=m ; ++i) {
        scanf("%lld",&c[i].d);
    }
    sort(c+1,c+m+1);
    for (int i = 1; i <=m ; ++i) {
        auto index=p.lower_bound(c[i].l);//lower_bound 代表第一个<=查找数的指针。
        if(index==p.end()){
            continue;//如果是空集就代表这张券不能用。
        }
        ans-=c[i].d;
        ma[*index]--;
        if(ma[*index]==0){
            p.erase(index);
        }
    }
    printf("%lld\n",ans);
    return 0;
}