题解 [ABC308F] Vouchers

cjh20090318 · 2023-07-03 08:20:05 · 题解

题意

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

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

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

问最小花费。

分析

很简单的一道贪心题，但是赛时没有想出来。

首先将每一个物品的价格按升序排列，每一张优惠券按 L 升序排列。

接着依次遍历 1 \sim n 的物品，将可以使用的优惠券加入进来。（即第 i 个物品，想要使用第 j 张优惠券必须满足的条件是 L_j \le P_i）

要求最大的 D，直接加入一个优先队列 priority_queue 即可。

代码

//the code is from chenjh
#include<cstdio>
#include<algorithm>
#include<queue>
int n,m;
int p[200002];
struct TIC{
    int l,d;
    TIC(int _l=0,int _d=0):l(_l),d(_d){}
    bool operator < (const TIC& y)const{return l<y.l;}//重载运算符。
}t[200002];
std::priority_queue<int> Q;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&p[i]);
    std::sort(p+1,p+n+1);//将物品价格升序排列。
    for(int i=1;i<=m;i++) scanf("%d",&t[i].l);
    for(int i=1;i<=m;i++) scanf("%d",&t[i].d);
    std::sort(t+1,t+m+1);//将优惠券升序排列。
    long long ans=0;
    for(int i=1,j=1;i<=n;i++){
        for(;j<=m && t[j].l<=p[i];j++)Q.push(t[j].d);
        int D=0;
        if(!Q.empty())
            D=Q.top(),Q.pop();//不为空（即有可用优惠券）就取出使用。
        ans+=p[i]-D;
    }
    printf("%lld\n",ans);
    return 0;
}