题解 P3045 【[USACO12FEB]牛券Cow Coupons】

题目传送门

Desprition

\(FJ\) 准备买一些新奶牛,市场上有 \(N\) 头奶牛、\(K\) 张优惠券,优惠劵可降价,每头奶牛只能使用一次优惠券。问知道花不超过 \(M\) 的钱最多可以买多少奶牛?

Solution

贪心 + 优先队列

首先,根据经验, \(k\) 张优惠券肯定是尽量全用的…… 不要白不要嘛

优惠券用不完的情况很好处理,下面只对钱有剩余还可以再买的情况进行分析。

可以得到几个条件(具体证明参见暮光闪闪的证明)

  • 优惠后价格最低的前 \(k\) 头牛一定在购买序列中;
  • 优惠券不一定会用在这前 \(k\) 头牛中;

所以当前需要研究的是怎样用剩余的钱买尽可能多余下的牛。(注意后文中牛的顺序是 按\(c_i\) 从小到大排序后的顺序)

对于一头牛 \(i\) ,有两种情况:

  • 不用券, 则多花费 \(p_i\) 元;
  • 用券,则多花费 \(c_i\) 元,但是现在假设的是 \(k\) 张券全部用在前 \(k\) 头牛,所以需要在用券前 \(k\) 中找出牛 \(j\),将券腾出来,那实际增加的花费应该为 \(c_i + p_j - c_j\) ;

又因为想买更多的牛,所以不管 \(p_i\) 还是 \(c_i\) 或者 \(c_i + p_j - c_j\),都要求花费最少。

因此用三个优先队列维护即可。

Code


#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define ll long long
const int N = 5e4 + 5;
struct node {
	int p,c,id;
}cow[N];
struct cmp {
	bool operator () (const node x,const node y) {return x.c > y.c;}	
};
struct cmp2 {
	bool operator () (const node x,const node y) {return x.p > y.p;}	
};
struct cmp3 {
	bool operator () (const node x,const node y) {return x.p - x.c > y.p - y.c;}	
};
priority_queue<node, vector<node>, cmp> q;
priority_queue<node, vector<node>, cmp2> q2;
priority_queue<node, vector<node>, cmp3> q3;
int n,k,ans;
ll m;
bool used[N];
int main() {
	scanf("%d %d %lld",&n,&k,&m);
	for(int i = 1; i <= n; i ++) {
		scanf("%d %d",&cow[i].p,&cow[i].c);
		cow[i].id = i, q.push(cow[i]), q2.push(cow[i]);
	}
	for(int i = 1; i <= min(n,k); i ++) {
		m -= q.top().c;
		if(m < 0) {printf("%d\n",ans); return 0;}
		ans ++, used[q.top().id] = 1;
		q3.push(q.top()), q.pop();
	}
	node x, y, z;
	for(int i = k + 1; i <= n; i ++) {
		while(used[q2.top().id]) q2.pop();
		while(used[q.top().id]) q.pop();
		x = q.top(), y = q2.top(), z = q3.top();
		if(y.p < x.c + z.p - z.c) m -= y.p, q3.push(y), used[y.id] = 1, q2.pop();
		else m -= x.c + z.p - z.c, used[x.id] = 1, q.pop(), q3.pop();
		if(m < 0) break;
		ans ++;
	}
	printf("%d",ans);
	return 0;
}

上一篇:POJ3263-Tallest Cow


下一篇:[USACO14OPEN]Fair Photography Bronze 题解