Cow Coupons G

· · 题解

Cow Coupons G

by jr_zch 博客食用更佳喵~

Part 1：蒟蒻的心声

USACO 一定是用脚做的数据吧！

题目要求输出一个数，我有一份代码输出了两个数，然后通过了 7 个测试点。

评测记录

Part 2：解题思路

O(n \log_2n)：正解如下

这种题目做多了自然会想到贪心或者 dp，但是观察到 1 \leq M \leq 10^{14}，直接排除用 dp 做的可能性。

容易想到，将奶牛按 C 递增排序后，前 k 头奶牛一定是要购买的。

那么剩下的奶牛呢？有两种情况：

  1. 全部用原价购买。

  2. 把前 k 头奶牛的优惠券转移到后面某一头牛上。

第一种情况处理起来很简单，排序或者用堆维护最小值，一直买，直到没钱为止。

第二种情况则是用小根堆维护前 k 头奶牛的差价（因为要让转移后的损失最小），每次取出堆顶并加上要购买奶牛的 c 值即为花费。然后再将这头奶牛加入小根堆。

但是！如果算出来的花费比直接买这头奶牛还要大，就选择原价购买，无需转移。

可以结合代码进行理解。

tips：

Part 3：Code

可以通过所有的 hack 数据

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

const int maxn=5e4+7;
int n,m,p,sum,fcost,scost,fans,sans;
struct node{
    int a,b,v;
}c[maxn];
priority_queue<int,vector<int>,greater<int> > q;

bool cmp(node x,node y){
    return x.b==y.b?x.a>y.a:x.b<y.b; //如果相等要按原价降序排，否则会像我一样被hack
}

signed main(){
    scanf("%lld%lld%lld",&n,&m,&p);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&c[i].a,&c[i].b),c[i].v=c[i].a-c[i].b;
    sort(c+1,c+1+n,cmp); //按 c 升序排序 
    //购买前 k 头牛 
    for(int i=1;i<=m;i++){
        if(sum+c[i].b<=p) sum+=c[i].b,q.push(c[i].v);
        else printf("%lld",i-1),exit(0); //前 k 头牛都买不完直接退出 
    }
    fcost=scost=sum,fans=sans=m;
    //上文中的情况 2 
    for(int i=m+1;i<=n;i++){
        //直接买更便宜 
        if(c[i].a<=c[i].b+q.top()&&fcost+c[i].a<=p) fcost+=c[i].a,fans++;
        //将优惠券进行转移 
        if(c[i].b+q.top()<c[i].a&&fcost+q.top()+c[i].b<=p){
            fcost+=c[i].b+q.top(),fans++;
            q.pop(),q.push(c[i].v);
        }
    }
    //复用堆，节省空间 
    while(q.size()) q.pop();
    //上文中的情况 1 
    for(int i=m+1;i<=n;i++) q.push(c[i].a);
    while(q.size()&&scost+q.top()<=p) scost+=q.top(),q.pop(),sans++;
    printf("%lld",max(fans,sans));
    return 0;
}

Thanks for your reading