题解：P3045 [USACO12FEB] Cow Coupons G

· · 题解

P3045 [USACO12FEB] Cow Coupons G(详细推导题解)

感觉本题写题解的大佬们讲的不够清楚，题解说的反悔贪心看得懂，但是在代码里面就看不到反悔的过程，而且反悔也不知道反悔的什么，百思不得其解。希望我这篇题解能详细地将本题的贪心讲明白。

贪心阶段一。

一开始，我们可以很容易地想到最简单的贪心策略。基础贪心策略：

  1. 将 每头牛 用优惠券买的价格 和 不用优惠券买的价格 统计在一起。

  2. 每次取出花钱最少的一个价格，如果剩下的钱不够买这头牛就结束，够买则判断；

  3. 如果这个价格不用优惠券买，就直接买；

    如果这个价格需要用优惠券买，如果还有优惠券就用掉一个优惠券来买，没优惠券了就跳过。

贪心阶段二。

但是自造数据测试，我们很快就能发现这个策略不是最优的。

3 2 6

5 1 (差为4)

3 1 (差为2)

6 2 (差为4)

如果我们采取刚才的策略，因为第一头和第二头牛用优惠券买的价格最小，我们会用掉两个优惠券买第一头和第二头牛，剩下来的钱不够买第三头牛，于是最终买了两头牛。但是如果我们用优惠券买第一头和第三头牛，最后会剩下三块钱，刚好能卖第二头牛，可以买三头牛。

哪个环节出问题了呢？用优惠券买第一头牛可以省下四块钱，用优惠券买第二头牛可以省下两块钱，用优惠券买第三头牛可以省下四块钱。我们可以发现，第三头牛省下的四块钱完全够买下第二头牛。这里就出问题了，优惠券的使用不是最佳的。于是我们用到反悔贪心，在先前的基础贪心策略上考虑上优惠券使用的策略。

划重点，这里我们反悔的不是 之前某头奶牛买不买，而是优惠券使用在哪头奶牛上，原因之后再阐释。通过转移优惠券的使用，我们可以省下优惠券省钱的差价，用于便宜购买新的奶牛。

例如刚才的数据，当我们进行基本贪心策略到了第三步，我们没有优惠券可以用了，这时我们发现如果在第三头牛上用优惠券，可以省下四块钱，而用在第二头奶牛上的优惠券只省下了两块钱。我们决定第二头牛不用优惠券，会多花 之前省下来的两块钱，将这个优惠券用在第三头奶牛上，我们会省下四块钱，(-2)+(4)=2，我们多省了两块钱，而第三头奶牛用优惠券买刚好用了两块钱，就可以多买一头牛了。这个转移优惠券过程中，第二头依然买下不动。即买的过程中，已经买的牛不会再变化，买的牛只会越来越多。

看不懂？我们将省钱换成赚钱理解。第二头奶牛不用优惠券，我们花了两块钱 (-2)；第三头奶牛用优惠券，我们赚了四块钱 (-2+4)；用优惠券买第三头奶牛，我们花了两块钱 (-2+4-2)。最终花的钱没有变化，但是我们多买了一头牛。

总结一下换票的过程。如果 C_j + (P_i - C_i) < P_j(P代表原价，C代表用券买的价格)。够钱没票的情况下，考虑第j头奶牛时，一种情况是用原价卖，另一种情况是转移优惠券，转移优惠券到这头牛上，用的钱为 这头牛用优惠券的价格 加上 前面用优惠券的第 i 头奶牛省下的差价。两种情况都会比之前多买第 j 头奶牛，这里采用贪心，取花钱更少的情况。

但是，这里我们出现了问题。用原价用的是什么原价呢？第j头奶牛的原价？显然，不用优惠券买第j头牛不等于要用原价买第j头牛，同样是用原价，我们为什么不选择更便宜的用原价买的牛呢？因此，这里的原价是最便宜的原价。这里也是理解的关键点。转换下语意，我们要将 采用 最便宜的优惠价 的 转移优惠券 的 情况 与 选择 最便宜的原价 的 情况作比较，原价和优惠价都是最便宜的价格，同时，转移优惠券时选择的优惠券应该也是省钱最少的优惠券，这是我们贪心的关键之一。修改下公式，C_j + (P_i - C_i) < P_k （C_j指最便宜的优惠价，(P_i-C_i)指优惠最少的优惠券省下的钱，P_k指最便宜的原价）时，我们进行优惠券转移。

为什么我们不反悔买不买奶牛呢？这非常复杂。如果我们不卖第二头奶牛，我们不是可以省下四块钱和一张优惠券吗吗？当我们排除第二头奶牛，用这个券买第三头奶牛。然后剩下来三块钱。这三块钱我们显然可以买第二头奶牛，最终我们还是买了三头牛。但是这个过程，发生了钱的变化，优惠券的变化，买奶牛头数的变化，同时我们考虑的价格也有顺序的调整（第二头牛不考虑就扔后面了）。既然如此，我们为什么不只考虑转移优惠券来省钱呢？反正我们不买这头牛，我们总会接着考虑剩下的钱能不能买这头牛。我们不妨将买过的牛固定，只考虑未买的牛和优惠券。这是一种固定变量，一种贪心思路的简化。（竞赛时我很可能想不到简化喵，这也是贪心的难点了。）

总结下改进后的贪心策略：

  1. 将每头牛用优惠券和价格和不用优惠券的价格按从小到大排序（同样价格的不用优惠券的放前面），放在两个队列里（此处用优先队列），按从小到大遍历两个队列。取最便宜的优惠价与最便宜的原价。同时我们用一个优先队列存储优惠券省下的钱（因为买下的牛，不管用不用券就不会再动，所以我们不需要考虑这个优惠券用在哪，只用考虑这个券省下多少钱就行了），并找到优惠最小的牛优惠了多少（差价）。
  2. 如果原价比优惠价便宜，钱够就直接买。钱不够就结束。
  3. 如果优惠价比原价便宜。
    1. 还有优惠券用，钱够就用优惠券买，不够就结束。
    2. 如果没优惠券用了，就比较之前优惠最小的牛。如果转移优惠券到这头牛，再补回之前优惠的差价，比用(最便宜)原价买更省钱的话，就转移优惠券。
    3. 如果转移优惠券不如原价买，就用原价买。不够就结束。

贪心阶段三。

理解刚才改进贪心策略后。在此基础上，我们还能进行优化。为何不一开始就将优惠券固定，将每个优惠券初始化为省了 0 元？这样我们就不用判断优惠券还有没有，可以空转优惠券。可以理解成如果还有剩余的优惠券，这个优惠券省钱为0，一定是省钱最少的那个，代入公式 C_j + (P_i - C_i) < P_k ，则 (P_i - C_i) 等于0， 等效于 C_j < P_k ，就是我们改进贪心策略中原价与优惠价的比较。因此我们还可以少去一步比较原价与优惠价的过程，将其直接融入反悔。优化后的改进贪心策略如下：

  1. 将每头牛用优惠券和价格和不用优惠券的价格按从小到大排序（同样价格的不用优惠券的放前面），放在两个队列里（此处用优先队列），按从小到大遍历两个队列。取最便宜的优惠价与最便宜的原价。同时我们用一个优先队列存储 每个优惠券省下的钱，默认为0。并找到优惠最小的牛优惠了多少（差价）。
  2. 如果转移优惠券到这头牛，再补回之前优惠的差价，比用(最便宜)原价买更省钱的话，就转移优惠券。

两种方法其实本质上是一样的，我看许多题解都直接跳到了改良之后，有点难以理解，于是我将基本贪心策略和改进贪心策略列了出来，方便理解。

代码实现。

然后用程序实现，两种策略都写了，可对照注释理解。

代码不算长的，只是为了可读性稍微多换了行，就不扔云剪贴板了（

改进后贪心策略写法：

//https://www.luogu.com.cn/problem/P3045
//Cuxhin、初心
#include<bits/stdc++.h>
#define N 500010
using namespace std;

long long n,k,m,s[N],sum=0,cnt=0;
//n头奶牛，k条券，m块钱，s代表第i个商品省下的钱，sum代表花的钱总数，cnt代表买了几头牛 
bool dic[N]={false};
//用来标记哪头奶牛买过的字典，买过就返回i

//奶牛 
class Cow{
public:
    long long page,value;
    //奶牛在字典上对应第几个，和买该奶牛需要用的钱（用优惠券或者不用优惠券的） 

    //无参构造 
    Cow(){}
    //有参构造 
    Cow(long long a,long long b):page(a),value(b){  }
    //奶牛是否买过（字典上是否标记） 
    bool check(){return dic[page];}
    //要买这头奶牛，在字典上标记它 
    void write(){dic[page]=true;return ;}
    //这头奶牛能省下多少钱 
    long long save(){return s[page];}
    //优先队列的比较函数，用的钱比较少的奶牛扔前面 
    //（用优惠券或者不用优惠券的） 
    friend bool operator<(Cow a,Cow b){
        return a.value>b.value;
    }
};

//优惠券 
class Ticket{
public:
    long long value;//这个优惠券省下来的钱 
    //无参构造 
    Ticket(){}
    //有参构造 
    Ticket(long long a):value(a){}
    //省下来的钱，const是因为优先队列内的Ticket是静态 
    long long save() const{return value;}
    //优先队列的比较函数，省钱比较少的奶牛扔前面 
    friend bool operator<(Ticket a,Ticket b){
        return a.value>b.value;
    }
};
//奶牛不用优惠券和用优惠券的临时变量 
Cow p_tmp,c_tmp;
//奶牛不用优惠券和用优惠券的优先队列 
priority_queue<Cow> p_que,c_que;
//优惠券的优先队列 
priority_queue<Ticket> ticket;
int main(){
    //优化输入 
    ios::sync_with_stdio();
    cin.tie(0);
    cout.tie(0);
    //输入奶牛数，优惠券数和钱数 
    cin>>n>>k>>m;
    //每个优惠券扔进队列，默认所有优惠券都没有省钱 
    for(int i=1;i<=n;i++){
        //输入第i头奶牛不用优惠券和用优惠券的价钱 
        long long p_itmp,c_itmp;
        cin>>p_itmp>>c_itmp;
        //第i头牛省下的钱 
        s[i]=p_itmp-c_itmp;
        //不用优惠券和用优惠券的钱分别扔进相关队列 
        p_que.push(Cow(i,p_itmp));
        c_que.push(Cow(i,c_itmp));
    }
/*未优化之前的朴素写法，用于理解贪心*/   //如果省钱和不省钱的队列其中一个为空，则所有奶牛都买过了
    while(!p_que.empty() and !c_que.empty()){
        //临时保存不用优惠券买奶牛需要花最少的钱
        //和用优惠券买奶牛需要花费最少的钱 
        p_tmp=p_que.top(),c_tmp=c_que.top();
        //如果用优惠券买过了 
        if(p_tmp.check()){
            p_que.pop();
            continue;
        }
        //如果不用优惠券买过了 
        if(c_tmp.check()){
            c_que.pop();
            continue;   
        } 
        if(p_tmp.value<c_tmp.value){//原价更便宜 
            sum+=p_tmp.value;//总花钱增加 
            p_que.pop();//原价的队列弹出 
            p_tmp.write();//字典标记这头奶牛表示已经买过 
        }
        else{//优惠券更便宜 
            if(ticket.size()<k){//还有优惠券 
                sum+=c_tmp.value;//总花钱增加 
                c_que.pop();//用优惠券买的队列弹出 
                c_tmp.write();//字典标记这头奶牛表示已经买过 
                //修改优惠券的队列 
                ticket.push(Ticket(c_tmp.save()));//用这个优惠券买这头奶牛省的钱弹进去 
            }
            else if(c_tmp.value + ticket.top().save() < p_tmp.value){//转移优惠券更便宜 
                sum+=c_tmp.value+ticket.top().save();//总花钱增加 
                c_que.pop();//用优惠券买的队列弹出 
                c_tmp.write();//字典标记这头奶牛表示已经买过 
                //修改优惠券的队列 
                ticket.pop();//优惠券的队列队头弹出 
                ticket.push(Ticket(c_tmp.save()));//用这个优惠券买这头奶牛省的钱弹进去 
            }
            else{//原价更便宜 
                sum+=p_tmp.value;//总花钱增加 
                p_que.pop();//原价的队列弹出 
                p_tmp.write();//字典标记这头奶牛表示已经买过 
            }
        }
        if(sum<=m){
            cnt++;//如果钱还够，就买成，总买的牛加一。 
        }
        else{
            break;//钱不够了，以后都买不成了。 
        }
    } 

    cout<<cnt;//输出能买的最多的牛 
    return 0;//剧终 
}

优化后的写法：

//https://www.luogu.com.cn/problem/P3045
//Cuxhin、初心
#include<bits/stdc++.h>
#define N 500010
using namespace std;

long long n,k,m,s[N],sum=0,cnt=0;
//n头奶牛，k条券，m块钱，s代表第i个商品省下的钱，sum代表花的钱总数，cnt代表买了几头牛 
bool dic[N]={false};
//用来标记哪头奶牛买过的字典，买过就返回i

//奶牛 
class Cow{
public:
    long long page,value;
    //奶牛在字典上对应第几个，和买该奶牛需要用的钱（用优惠券或者不用优惠券的） 

    //无参构造 
    Cow(){}
    //有参构造 
    Cow(long long a,long long b):page(a),value(b){}
    //奶牛是否买过（字典上是否标记） 
    bool check(){return dic[page];}
    //要买这头奶牛，在字典上标记它 
    void write(){dic[page]=true;return ;}
    //这头奶牛能省下多少钱 
    long long save(){return s[page];}
    //优先队列的比较函数，用的钱比较少的奶牛扔前面 
    //（用优惠券或者不用优惠券的） 
    friend bool operator<(Cow a,Cow b){
        return a.value>b.value;
    }
};

//优惠券 
class Ticket{
public:
    long long value;//这个优惠券省下来的钱 
    //无参构造 
    Ticket(){}
    //有参构造 
    Ticket(long long a):value(a){}
    //省下来的钱，const是因为优先队列内的Ticket是静态 
    long long save() const{return value;}
    //优先队列的比较函数，省钱比较少的奶牛扔前面 
    friend bool operator<(Ticket a,Ticket b){
        return a.value>b.value;
    }
};
//奶牛不用优惠券和用优惠券的临时变量 
Cow p_tmp,c_tmp;
//奶牛不用优惠券和用优惠券的优先队列 
priority_queue<Cow> p_que,c_que;
//优惠券的优先队列 
priority_queue<Ticket> ticket;
int main(){
    //优化输入 
    ios::sync_with_stdio();
    cin.tie(0);
    cout.tie(0);
    //输入奶牛数，优惠券数和钱数 
    cin>>n>>k>>m;
    //每个优惠券扔进队列，默认所有优惠券都没有省钱 
    for(int i=1;i<=n;i++){
        //输入第i头奶牛不用优惠券和用优惠券的价钱 
        long long p_itmp,c_itmp;
        cin>>p_itmp>>c_itmp;
        //第i头牛省下的钱 
        s[i]=p_itmp-c_itmp;
        //不用优惠券和用优惠券的钱分别扔进相关队列 
        p_que.push(Cow(i,p_itmp));
        c_que.push(Cow(i,c_itmp));
    }

/*优化后的写法*/
    //初始化优惠券队列。
    for(int i=1;i<=k;i++) ticket.push(Ticket(0));
    //如果省钱和不省钱的队列其中一个为空，则所有奶牛都买过了
    while(!p_que.empty() and !c_que.empty()){
        //临时保存不用优惠券买奶牛需要花最少的钱
        //和用优惠券买奶牛需要花费最少的钱 
        p_tmp=p_que.top(),c_tmp=c_que.top();
        //如果用优惠券买过了 
        if(p_tmp.check()){
            p_que.pop();
            continue;
        }
        //如果不用优惠券买过了 
        if(c_tmp.check()){
            c_que.pop();
            continue;   
        } 
        //不用优惠券更省钱 
        if(p_tmp.value<c_tmp.value+ticket.top().save()){
            sum+=p_tmp.value;//总花钱增加 
            p_que.pop();//原价的队列弹出 
            p_tmp.write();//字典标记这头奶牛表示已经买过 
        }
        else{
            sum+=c_tmp.value+ticket.top().save();//总花钱增加 
            c_que.pop();//用优惠券买的队列弹出 
            c_tmp.write();//字典标记这头奶牛表示已经买过 
            //修改优惠券的队列 
            ticket.pop();//优惠券的队列队头弹出 
            ticket.push(Ticket(c_tmp.save()));//用这个优惠券买这头奶牛省的钱弹进去 
        }
        if(sum<=m){
            cnt++;//如果钱还够，就买成，总买的牛加一。 
        }
        else{
            break;//钱不够了，以后都买不成了。 
        }
    }
    cout<<cnt;//输出能买的最多的牛 
    return 0;//剧终 
}

总结反思。

本题是很好的一道练习反悔贪心的题目，在思考贪心策略的时候应该循序渐进，步步深入改良，不要一步登天。我们可以通过固定一些变量来辅助我们明确贪心策略。如本题固定了奶牛数量。然后在一些关键的值考虑取最值来实现贪心。就到这了吧，谢谢观看。