AT [ABC308F] Vouchers

FreedomKing · 2023-07-04 20:29:46 · 题解

懂了之后感觉好简单啊，这个难度放 D 差不多吧。

思路

因为此题要做到优惠劵的利用最大化，所以直接贪心。

考虑先给较便宜的物品其能使用的最优优惠劵，可以直接对物品进行升序排序，然后依靠使用每张优惠劵所需要的最少金额升序排序，遍历一遍物品，当某张优惠劵能作用于第 i 件物品，就将他能优惠的金额加入到可用序列中，最后每次都使用掉这个物品能使用的最大优惠金额的优惠劵即可，这个可用优惠劵序列直接使用优先队列维护即可。

剩下不懂的可以看代码中的注释。

AC Code

#include<bits/stdc++.h>
#define int long long//第一次交的时候没开寄了
using namespace std;
const int N=1e6+5;
int a[N],n,m,t,k;
priority_queue<int>pq;
struct node{
    int l,d;
}f[N];
bool cmp(node x,node y){
    return x.l<y.l;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>f[i].l;
    for(int i=1;i<=m;i++) cin>>f[i].d;
    sort(a+1,a+n+1);
    //升序排序后面的物品就一定能用上前面物品能用的优惠卷了
    sort(f+1,f+m+1,cmp);
    t=1;
    for(int i=1;i<=n;i++){
        while(t<=m&&f[t].l<=a[i]){//寻找所有当前能使用的优惠劵
            pq.push(f[t].d);
            t++;
        }
        k+=a[i];
        if(!pq.empty()){//如果还有优惠劵
            k-=pq.top();
            pq.pop();
        }
    }
    cout<<k;
    return 0;
}