[USACO12FEB]牛券Cow Coupons

题目描述

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头奶牛(1<=N<=50000)，第i头奶牛价格为Pi(1<=Pi<=10^9)。FJ有K张优惠券，使用优惠券购买第i头奶牛时价格会降为Ci(1<=Ci<=Pi)，每头奶牛只能使用一次优惠券。FJ想知道花不超过M(1<=M<=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：

说明

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.

分析：

本题较难，但是根据题目不难得出本题的算法：贪心和堆，因此本题只是实现算法的问题，也就是考验编程能力。

CODE:

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <queue>
 7 #define M 1000000
 8 using namespace std;
 9 int n,k,ans,to[M];
10 long long m;
11 int read(){
12     char c=getchar();int ans=0;
13     while (c<'0'||c>'9') c=getchar();
14     while (c>='0'&&c<='9') ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();
15     return ans;
16 }
17 struct node{
18     int x,y,id;
19 }a[M],b[M],c[M];
20 bool cmp1(node u,node v){return u.y<v.y;}
21 bool cmp2(node u,node v){return u.x<v.x;}
22 bool cmp3(node u,node v){return u.x-u.y<v.x-v.y;}
23 int main(){
24     n=read(),k=read();scanf("%lld",&m);
25     for (int i=1;i<=n;++i) a[i].x=b[i].x=c[i].x=read(),a[i].y=b[i].y=c[i].y=read(),a[i].id=b[i].id=c[i].id=i;
26     sort(a+1,a+1+n,cmp1);sort(b+1,b+1+n,cmp2);sort(c+1,c+1+n,cmp3);
27     for (int i=1;i<=k;++i){
28         if (m<a[i].y){printf("%d",ans);return 0;}
29         m-=a[i].y;++ans;to[a[i].id]=1;
30     }
31     int now_a=k+1,now_b=1,now_c=1;
32     while (to[b[now_b].id]) ++now_b;
33     while (!to[c[now_c].id]) ++now_c;
34     while (ans<n){
35         int tmp1=b[now_b].x,tmp2=c[now_c].x-c[now_c].y+a[now_a].y;
36         if (m<tmp1&&m<tmp2) break;
37         ++ans;
38         if (tmp1<tmp2) m-=b[now_b].x,to[b[now_b++].id]=1;
39         else m-=(c[now_c].x-c[now_c].y+a[now_a].y),now_c++,to[c[now_c++].id]=1;
40         while (now_b<=n&&to[b[now_b].id]) ++now_b;
41         while (now_c<=n&&!to[c[now_c].id]) ++now_c;
42     }
43     printf("%d",ans);
44     return 0;
45 }