「BZOJ2590」[Usaco2012 Feb] Cow Coupons
Description
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? PROBLEM NAME: coupons
FJ准备买一些新奶牛，市场上有N头奶牛(1<=N<=50000)，第i头奶牛价格为Pi(1<=Pi<=10^9)。FJ有K张优惠券，使用优惠券购买第i头奶牛时价格会降为Ci(1<=Ci<=Pi)，每头奶牛只能使用一次优惠券。FJ想知道花不超过M(1<=M<=10^14)的钱最多可以买多少奶牛？
Input
* 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.
Output
* Line 1: A single integer, the maximum number of cows FJ can afford.
Sample Input
3 2
2 2
8 1
4 3
Sample Output
OUTPUT DETAILS: FJ uses the coupon on cow 3 and buys cows 1, 2, and 3, for a total cost of 3 + 2 + 1 = 6.
题解
先用优惠券卖C前K小的牛，在最小堆中加入P-C
将剩下的牛按照P升序排序
依次购买
1.花费P
2.花费q.top()，获得优惠券，花费C，在堆中加入P-C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include<cmath> #include<queue> #include<vector> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pa pair<int,int> #define inf 1000000000 #define eps 1e-8 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } priority_queue<int,vector<int>,greater<int> >q; int n,K,ans; ll m,sum; struct data{ int p,c; }a[50005]; bool cmpc(data a,data b) { return a.c<b.c; } bool cmpp(data a,data b) { return a.p<b.p; } int main() { n=read();K=read();m=read(); for(int i=1;i<=n;i++) a[i].p=read(),a[i].c=read(); sort(a+1,a+n+1,cmpc); for(int i=1;i<=K;i++) { sum+=a[i].c; q.push(a[i].p-a[i].c); if(sum>m){printf("%d\n",i-1);return 0;} if(i==n){printf("%d\n",n);return 0;} } sort(a+K+1,a+n+1,cmpp); ans=K; for(int i=K+1;i<=n;i++) { int t=inf; if(!q.empty())t=q.top(); if(t<a[i].p-a[i].c) { sum+=t;q.pop(); q.push(a[i].p-a[i].c); sum+=a[i].c; } else sum+=a[i].p; if(sum>m)break; else ans++; } printf("%d\n",ans); return 0; } |
OI 课件=>
Hack !!!
3 1 63 2
100 100
101 3
答案该是2，也就是原价购买第一头和优惠购买第三头。
黄学长这样的话也就是钦定了C前k小的牛是必须选的了？ 但是这个如何证明呢？