首页 > 其他 > 详细

P3045 [USACO12FEB]牛券Cow Coupons

时间:2020-02-17 14:02:59      阅读:43      评论:0      收藏:0      [点我收藏+]

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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!