题目链接

牛券

题目描述

Farmer John needs new cows! There are $N$ cows for sale $(1 \le N \le 50,000)$, and FJ has to spend no more than his budget of $M$ units of money $(1 \le M \le 10^{14})$. Cow $i$ costs $P_i$ money $(1 \le P_i \le 10^9)$, but FJ has $K$ coupons $(1 \le K \le N)$, and when he uses a coupon on cow $i$, the cow costs $C_i$ instead $(1 \le C_i \le 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 \le N \le 50000)$,第i头奶牛价格为$Pi(1 \le Pi \le 10^9)$。FJ有$K$张优惠券,使用优惠券购买第$i$头奶牛时价格会降为$Ci(1 \le Ci \le Pi)$,每头奶牛只能使用一次优惠券。FJ想知道花不超过$M(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.

样例输入

4 1 7 
3 2 
2 2 
8 1 
4 3 

样例输出

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$.

题解

题意:你有$M$块钱,有$N$个奶牛,每个奶牛都有原价和优惠价,你有$K$个优惠券。
你可以用原价买奶牛或者使用一个优惠券用优惠价买奶牛,求$M$块钱最多能卖多少奶牛。
这里我们很容易想到使用贪心。
因为优惠价一定小于等于原价,所以我们按优惠价从小到大排序。
如果还有优惠券能用,那么我们就使用优惠券。(在钱还够的情况下)
如果没有优惠券了,那么我们有两种选择:

  1. 用原价购买这个牛
  2. 在已使用优惠券的牛中选择一个牛,使得这个牛不适用优惠券后增加的价格最小,把这个牛的优惠券给当前牛用。
    注:以上两种情况都要在钱够用的情况下

然后我们发现如果暴力找第二种选择时间复杂度就是$O(n^2)$,所以我们可以用优先队列维护priority_queue<int,vector<int>,greater<int> >。
当然如果您很强,不屑于用我这种菜鸡用的优先队列,您也可以手打堆来维护。
综上所述,时间复杂度为$O(nlogn)$
上代码:

#include<bits/stdc++.h>
#include<queue>
using namespace std;
int n,k;
long long m;
struct aa{
    int p,c;
}a[50009];
int ans;
priority_queue<int,vector<int>,greater<int> >q;
bool cmp(aa x,aa y){return x.c<y.c;}
int main(){
    scanf("%d%d%lld",&n,&k,&m);
    for(int j=1;j<=n;j++)
        scanf("%d%d",&a[j].p,&a[j].c);
    sort(a+1,a+n+1,cmp);
    for(int j=1;j<=n;j++){
        if(k){
            if(m-a[j].c<0) continue;
            k--;
            m-=a[j].c;
            q.push(a[j].p-a[j].c);
            ans++;
        }else{
            if(m-min(a[j].p,a[j].c+q.top())<0) continue;
            m-=min(a[j].p,a[j].c+q.top());
            ans++;
            if(a[j].p-a[j].c>q.top()){
                q.pop();
                q.push(a[j].p-a[j].c);
            }
        }
    }
    printf("%d",ans);
    return 0;
}