P3045 [USACO12FEB]牛券Cow Coupons

系统管理员 2023-06-01 15:00 20阅读 0赞

### 洛谷 P3045 \[USACO12FEB\]牛券Cow Coupons ###

[题目描述][Link 1]

一个错误的贪心思路：设优惠券有无数张，然后我们贪心去选，这样就会得到94的好成绩。（数据真水

#include<algorithm> #include<iostream> #include<cstdio> #include<queue> #define ll long long using namespace std; const int N=5e4+100; ll n,k,m; struct info{ ll p,c; }id[N]; struct cmp1{ inline bool operator () (info a,info b) {return a.c>b.c;} }; struct cmp2{ inline bool operator () (info a,info b) {return a.p>b.p;} }; inline bool cmp(info a,info b) {return a.c<b.c;} int main() { scanf("%lld%lld%lld",&n,&k,&m); for (int i=1;i<=n;i++) scanf("%lld%lld",&id[i].p,&id[i].c); ll now=0,num=0; sort(id+1,id+n+1,cmp); for (int i=1;i<=n;i++) { if (now+id[i].c>m) break; now+=id[i].c; num++; } printf("%lld\n",num); return 0; }

这个题目的主要思路是贪心，首先我们先把用优惠券的\\(k\\)小个先拿出来代表用优惠券，这样可能会出错,但是我们再后面可以进行“反悔”操作，首先我们把选择的牛`p-c`压到小根堆里。

为啥要压到小根堆里？

因为`p-c`小的可以看做优惠力度不够，在进行反悔操作时把它拿出来的可能性比较大。

然后如果满足下面的式子

\\\[c\_j+p\_i<c\_i+p\_j\\\]

左面相当于\\(j\\)使用优惠券，i不用，右面相反

显然选\\(j\\)使用优惠券的费用比价少，所以我们选择\\(j\\)使用优惠券（和国王游戏有些类似。

因为我们后来是按照原价排的，所以不满足上面的条件直接选原价。

但我感觉还是有覅问题，因为这样的话，c排名前k小的肯定会被选,应该有些问题。暂时 Hash不掉请忽略

// luogu-judger-enable-o2 #include<algorithm> #include<iostream> #include<cstdio> #include<queue> #define ll long long using namespace std; const int N=5e4+100; struct info{ ll p,c,val; }id[N]; struct cmp1{ inline bool operator () (info a,info b) {return a.val>b.val;} }; priority_queue<info,vector<info>,cmp1>q; ll n,k,m; inline bool cmp2(info a,info b) {return a.c<b.c;} inline bool cmp3(info a,info b) {return a.p<b.p;} int main() { scanf("%lld%lld%lld",&n,&k,&m); for (int i=1;i<=n;i++) { ll x,y; scanf("%lld%lld",&x,&y); id[i]=(info){x,y,x-y}; } sort(id+1,id+n+1,cmp2); ll sum=0,ans=0; for (int i=1;i<=k;i++) { if (sum+id[i].c>m) { printf("%lld",ans); return 0; } sum+=id[i].c; q.push(id[i]); ans++; } sort(id+k+1,id+n+1,cmp3); for (int i=k+1;i<=n;i++) { info now=q.top(); if (now.p+id[i].c<now.c+id[i].p) { sum-=now.c; sum+=now.p+id[i].c; ans++; q.pop(); q.push(id[i]); } else { ans++; sum+=id[i].p; } if (sum>m) { printf("%lld\n",ans-1); return 0; } } printf("%lld\n",n); return 0; }

转载于:https://www.cnblogs.com/last-diary/p/11402205.html

[Link 1]: https://www.luogu.org/problem/P3045