P3045 Cow Coupons G

题面

USACO12FEBCow Coupons G 题面

题目背景

Subtask 0 为原数据，Subtask 1 为 hack 数据。

题目描述

Farmer John needs new cows! There are N cows for sale (1 <= N <= 50,000), and FJ has to spend no more than his budget of M units of money (1 <= M <= 10^14). Cow i costs P_i money (1 <= P_i <= 10^9), but FJ has K coupons (1 <= K <= N), and when he uses a coupon on cow i, the cow costs C_i instead (1 <= C_i <= P_i). FJ can only use one coupon per cow, of course.

What is the maximum number of cows FJ can afford?

FJ 准备买一些新奶牛。市场上有 $N$ 头奶牛，第 $i$ 头奶牛价格为 $P_i$。FJ 有 $K$ 张优惠券，使用优惠券购买第 $i$ 头奶牛时价格会降为 $C_i$，当然每头奶牛只能使用一次优惠券。FJ 想知道花不超过 $M$ 的钱最多可以买多少奶牛？

• $1 \le K \le N \le 5 \times 10^4$
• $1 \le C_i \le P_i \le 10^9$
• $1 \le M \le 10^{14}$

输入格式

* Line 1: Three space-separated integers: N, K, and M.

* Lines 2…N+1: Line i+1 contains two integers: P_i and C_i.

输出格式

* Line 1: A single integer, the maximum number of cows FJ can afford.

样例 #1

样例输入 #1

4 1 7 
3 2 
2 2 
8 1 
4 3

样例输出 #1

3

提示

FJ has 4 cows, 1 coupon, and a budget of 7.

FJ uses the coupon on cow 3 and buys cows 1, 2, and 3, for a total cost of 3 + 2 + 1 = 6.

解法

这很明显，是道贪心。

上来作者表示先骗分

于是就写了下面这一串东西：

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
#define int long long
int n,k,m,cnt=0;
int P[N],C[N];
struct cow{
    int id,val,kal;
    cow(){}
    cow(int x,int y,int z){id=x;val=y;kal=z;}
}co[N];
bool operator<(const cow &a,const cow &b)
{
    return a.val>b.val;
}
int ans=0;
bool cmp(cow a,cow b)
{
    return a.kal<b.kal;
}
priority_queue<cow> q;
signed main()
{
    scanf("%lld%lld%lld",&n,&k,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&P[i],&C[i]);
        co[i].id=i;
        co[i].val=P[i];
        co[i].kal=C[i];
    }
    sort(co+1,co+1+n,cmp);
    for(int i=1;i<=k;i++)
    {
        cnt++;
        ans+=co[i].kal;
        co[i].val=INT_MAX;
        if(ans>m)
        {
            cnt--;
            printf("%lld",cnt);
            return 0;
        }
    }
    for(int i=1;i<=n;i++)
    {
        q.push(co[i]);
    }
    while(!q.empty())
    {
        cnt++;
        ans+=q.top().val;
        q.pop();
        if(ans>m)
        {
            cnt--;
            printf("%lld",cnt);
            return 0;
        }
    }
    return 0;
}

很不幸，虽然过了一个substack，但是依旧零分（不让骗分呜呜呜）。

然后想想这个到底该怎么贪。

有K张优惠券，如果只买K头牛的话，那么一定是买优惠价为前K的牛最优，这毋庸置疑。

那么如果是K+1头呢？

新加了一只牛，它的优惠幅度比我优惠价为前K的某只牛更大，也就是打的折更多，这样显然用优惠价购买优惠幅度大的用原价购买优惠幅度低的更优。

那么回到N头牛的情况：

首先先把K张优惠券都用到C大小为前K小的牛上，然后考虑转移。

对于下一头奶牛，要么就是原价购买，要么就是转移优惠券购买，取更优的情况购买。

这里维护三个优先队列，一个存储牛的优惠价，一个存储原价，一个存储优惠价与原价的差价（都是小根堆）。

每次选出差价最小的（也就是优惠幅度最低的），然后把它的优惠券转移到还没有用优惠券C值最小的牛身上，这样总价值就是原来的加上最小的差价再加上最小的优惠价，

然后拿它和购买最小原价的情况作比较价格，谁小就按谁的方式买。

代码：

#include<bits/stdc++.h>
#define LL long long
#define pa pair<LL,int>
using namespace std;
priority_queue< pa,vector<pa>,greater<pa> >h1,h2;
priority_queue< LL,vector<LL>,greater<LL> >h3;
LL p[50100],c[50100],m,sum;
bool v[50100];
LL ans;
int main(){
	int n,k;
	scanf("%d%d%lld",&n,&k,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&p[i],&c[i]);
		h1.push(pa(p[i],i));
		h2.push(pa(c[i],i));
	}
	for(int i=1;i<=k;i++) h3.push(0LL);
	while(!h1.empty()){
		pa n1=h1.top();
		pa n2=h2.top();
		if(v[n1.second]){
			h1.pop();
			continue;
		}
		if(v[n2.second]){
			h2.pop();
			continue;
		}
		if(n1.first<n2.first+h3.top()){//说明不用优惠卷，或者优惠卷用完了后的代价太大，不如直接买 
			if(sum+n1.first>m) break;
			ans++;
			sum+=n1.first;
			v[n1.second]=true;
			h1.pop();
		}
		else{//如果h3.top()不为0，说明优惠卷已经用完，这时只能回退优惠卷并承担代价 
			if(sum+n2.first+h3.top()>m) break;
			ans++;
			sum+=n2.first+h3.top();
			v[n2.second]=true;
			h3.push(p[n2.second]-c[n2.second]);//差价，相当于回退优惠卷时要返回的代价 
			h2.pop();
			h3.pop();
		} 
	}
	printf("%lld\n",ans); 
	return 0;
}

不开long long见祖宗

---