P3045 Cow Coupons G

· · 题解

Blog 传送门

题目传送门

解法

这很明显，是道贪心。

第一感觉是能打折的按照打折价格从低到高买了，不能打折的就按照原价从低到高买了。

很不幸，虽然过了一个 Substack，但是依旧零分（不让骗分呜呜呜）。

想想这个到底该怎么贪。

有 K 张优惠券，如果只买 K 头牛的话，那么一定是买优惠价为前 K 的牛最优，这毋庸置疑。

那么如果是 K+1 头呢？

新加了一只牛，它的优惠幅度比我优惠价为前 K 的某只牛更大，也就是打的折更多，这样显然用优惠价购买优惠幅度大的用原价购买优惠幅度低的更优。

那么回到 N 头牛的情况：

首先先把 K 张优惠券都用到 C 大小为前 K 小的牛上，然后考虑转移。

对于下一头奶牛，要么就是原价购买，要么就是转移优惠券购买，取更优的情况购买。

这里维护三个优先队列，一个存储牛的优惠价，一个存储原价，一个存储优惠价与原价的差价（都是小根堆）。

每次选出差价最小的（也就是优惠幅度最低的），然后把它的优惠券转移到还没有用优惠券 C 值最小的牛身上，这样总价值就是原来的加上最小的差价再加上最小的优惠价，

然后拿它和购买最小原价的情况作比较价格，谁小就按谁的方式买。

代码：

#include<bits/stdc++.h>
#define LL long long//不开 long long 见祖宗
#define pa pair<LL,int>
using namespace std;
priority_queue< pa,vector<pa>,greater<pa> >h1,h2;
priority_queue< LL,vector<LL>,greater<LL> >h3;
LL p[50100],c[50100],m,sum;
bool v[50100];
LL ans;
int main(){
    int n,k;
    scanf("%d%d%lld",&n,&k,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&p[i],&c[i]);
        h1.push(pa(p[i],i));
        h2.push(pa(c[i],i));
    }
    for(int i=1;i<=k;i++) h3.push(0LL);
    while(!h1.empty()){
        pa n1=h1.top();
        pa n2=h2.top();
        if(v[n1.second]){
            h1.pop();
            continue;
        }
        if(v[n2.second]){
            h2.pop();
            continue;
        }
        if(n1.first<n2.first+h3.top()){//说明不用优惠卷，或者优惠卷用完了后的代价太大，不如直接买 
            if(sum+n1.first>m) break;
            ans++;
            sum+=n1.first;
            v[n1.second]=true;
            h1.pop();
        }
        else{//如果h3.top()不为0，说明优惠卷已经用完，这时只能回退优惠卷并承担代价 
            if(sum+n2.first+h3.top()>m) break;
            ans++;
            sum+=n2.first+h3.top();
            v[n2.second]=true;
            h3.push(p[n2.second]-c[n2.second]);//差价，相当于回退优惠卷时要返回的代价 
            h2.pop();
            h3.pop();
        } 
    }
    printf("%lld\n",ans); 
    return 0;
}