P3045 [USACO12FEB]牛券Cow Coupons

P3045 [USACO12FEB]牛券Cow Coupons

贪心题。先选中 \(c_i\) 最小的 \(k\) 头牛，如果这样就超过 \(m\) ，直接退出，输出答案。否则考虑把后面的牛依次加入，替换前面用过券的牛。这里贪心得选择省钱最少的牛替换掉（这样影响最小，最有可能多买几头）。加入牛的顺序按照 \(p\) 从小到大，因为如果换不掉就只能话 \(p\) 的钱去买

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M = 100005;
const int inf = 100000000000009;
struct node {
    int p,c;
} a[M];
int n,m,k,ans,now;
priority_queue<int,vector<int>,greater<int> > q;
bool cmp1(const node &x,const node &y) {return x.c < y.c;}
bool cmp2(const node &x,const node &y) {return x.p < y.p;}
signed main() {
    scanf("%lld%lld%lld",&n,&k,&m);
    for(int i=1;i<=n;++i)scanf("%lld%lld",&a[i].p,&a[i].c);
    sort(a+1,a+1+n,cmp1);
    for(int i=1;i<=k;++i){
        now+=a[i].c;
        if(now>m)return printf("%lld\n",i-1),0;
        q.push(a[i].p-a[i].c);
    }
    sort(a+k+1,a+1+n,cmp2);
    ans=k;
    for(int i=k+1;i<=n;++i){
        int tmp=(!q.empty())?q.top():inf;
        if(a[i].p-a[i].c>tmp)now+=tmp+a[i].c,q.pop(),q.push(a[i].p-a[i].c);
        else now+=a[i].p;
        if(now>m)break;
        else ++ans;
    }
    printf("%lld\n",ans);
    return 0;
}

另外说一句，洛谷上这题的题解大部分是伪的，尤其是头两篇。洛谷的数据真的水，那两篇也能AC，不但方法烦，还是错的。交到校网上全RE

P3045 [USACO12FEB]牛券Cow Coupons

原文：https://www.cnblogs.com/zzctommy/p/12321128.html