P3045 [USACO12FEB]Cow Coupons G

_ZSR_ · 2023-04-18 20:01:38 · 题解

P3045 [USACO12FEB]Cow Coupons G

读完题后我们发现并没有什么好的思路，可以考虑先把 k 张优惠卷用在 k 个最小的 c 的奶牛上，然后再做调整。

那么该如何调整优惠券的使用呢？我们可以开三个优先队列，一个存每一头牛的原价，一个存每一头奶牛使用优惠卷后的价格，一个存放原价和使用优惠卷后的价格的差。一开始先把所有的原价和优惠价放入队列，然后在存放差值的队列中放入 k 个 0，表示使用 k 张优惠卷，即不用补差价。

接着便是调整优惠卷的使用。我们每一次取出存放原价和优惠价的队列的队头，根据贪心，如果按原价买更便宜，我们就按原价买，如果按优惠价买并且补上差价更便宜，我们就使用优惠卷。最后，我们把这头奶牛打上标记，防止之后再被取出。

code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=50010;
typedef pair<int,int> pii;
int n,k,m;
int p[N],c[N];
bool st[N];
priority_queue<pii,vector<pii>,greater<pii>> qp,qc;
priority_queue<int,vector<int>,greater<int>> qd;
signed main()
{
    scanf("%lld%lld%lld",&n,&k,&m);
    for (int i=1;i<=n;++i)
    {
        scanf("%lld%lld",&p[i],&c[i]);
        qp.push({p[i],i});
        qc.push({c[i],i});
    }
    for (int i=1;i<=k;++i) qd.push(0);
    int sum=0,tot=0;
    while (qp.size())
    {
        auto tp=qp.top();
        auto tc=qc.top();
        if (st[tp.second])//之前用过
        {
            qp.pop();
            continue;
        }
        if (st[tc.second])//之前用过
        {
            qc.pop();
            continue;
        }
        if (tp.first<tc.first+qd.top())//按原价更便宜
        {
            if (sum+tp.first>m) break;
            sum+=tp.first;
            tot++;
            qp.pop();
            st[tp.second]=true;
        }
        else //拿一张之前用过的优惠卷过来用到这头奶牛上
        {
            if (sum+tc.first+qd.top()>m) break;
            sum+=tc.first+qd.top();
            tot++;
            qc.pop();
            st[tc.second]=true;
            qd.pop();
            qd.push({p[tc.second]-c[tc.second]});
        }
    }
    printf("%lld\n",tot);
    return 0;
}