题解 P3045 [USACO12FEB] Cow Coupons G

InfiniteHorizon · 2023-07-26 18:36:42 · 题解

这是反悔贪心的一道好题。

有人问，反悔贪心是什么？

其实贪心本身不带有反悔，是因为此时的贪心可以从局部最优解推出全局最优解。但当有些时候局部最优解推不出全局最优解时，就要用反悔贪心，在适当的时候撤销之前做出的决策。

我们先选取 c 最小的 k 个物品使用优惠劵，当前已经使用的价格是 tot。下文为方便表述，记使用优惠劵的物品集合为 A，他在求解过程中不是固定不变的。

当前考虑第 i 个物品，由于 k 张优惠券已经用完了，所以只能以原价 p_i 购买物品 i。现在考虑反不反悔的条件是什么。

如果要反悔，那么用优惠券买 i 的价格一定要小于用原价买 i。当 i 用了优惠券，那么 A 势必要有一个物品（记为 j,j \in A）做出退让，用原价来买 j。（其实相当于用 i 来代替 j），那么一定满足以下不等式：

意思是：i 代替 j 用优惠券的价格比用原价买 i 便宜，这个时候就需要反悔。

发现 tot 可以消去：

然后把下标相同的归在小于号的同一侧：

他们的形式是相同的，所以我们可以设 \Delta_i=p_i-c_i：

所以只要在已经使用优惠券的物品里面，存在一个 j，使得 \Delta_j<\Delta_i，我们就需要用 i 代替 j 使用优惠券。也就是 k 个物品中，(\Delta_j)_{\min}<\Delta_i 。注意这个不是恒等式，因为 i \notin A，但是 j\in A。

最小值可以用优先队列来求。

话不多说，上代码，代码中用 delta 优先队列存储了上文中提到的 \Delta_j,j\in A，P 存储原价 p_i，C 存储优惠价 c_i。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxn=50010;

int n,k,m;
int p[maxn],c[maxn];
bool buy[maxn];//buy[i] 表示第 i 个物品是否被买过
int ans=0;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >P,C;
priority_queue<int,vector<int>,greater<int> >delta;

signed main(){
    cin>>n>>k>>m;
    for(int i=1;i<=n;++i){
        cin>>p[i]>>c[i];
        P.push(make_pair(p[i],i));
        C.push(make_pair(c[i],i));
    }
    for(int i=1;i<=k;++i) delta.push(0);
    while(!P.empty()){
        pair<int,int> x1=P.top();
        pair<int,int> x2=C.top();
        if(buy[x1.second]){//如果被买过了，就跳过
            P.pop();
            continue;
        }
        if(buy[x2.second]){
            C.pop();
            continue;
        }
        if(delta.top() > x1.first-x2.first){//这个式子和上文推的式子时相反的，表示用原价买 i 更划算
            m-=x1.first;
            P.pop();
            buy[x1.second]=true;
        }
        else{//否则的话，就是用优惠券买 i 更划算
            m-=x2.first+delta.top();
            delta.pop();
            C.pop();
            buy[x2.second]=true;
            delta.push(p[x2.second]-c[x2.second]);
        }
        if(m>=0) ans++;
        else break;
    }
    cout<<ans<<endl;
    return 0;
}

最后，希望大家都能真正理解返回贪心，它的精髓就是“常思己过”！

静坐常思己过，闲谈莫论人非。——明 · 罗洪先《醒世诗》