傻逼买牛 | FJ

复制的题目

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

Sample Output

3
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.
傻逼后悔贪心然鹅我WA了三遍
贪心法应该是比较容易想到的吧
贪心原则把优惠券败光用完
然后我们就可以想到一个非常有意思的做法，按优惠价从小到大排序，前k张用优惠券
然而这样做是错的，因为枚举当前点时不会考虑对后面的影响，排序仅仅是按照优惠价排序的，那么如果后面的牛是否使用优惠券价格差大于前面（即省的钱更多）时，这个贪心法就是错误的了，上面这个贪心我们可以轻松卡掉
那么，我们可不可以按照省钱的多少从小到大排序取前几个呢？？？？？
…………用上面这个贪心法的同学出门右转谢谢
但是我们又可以想出一个结论，优惠价低的可能原价很低，不需要用优惠券来节省
贪心的策略是走一步看一步，不能考虑到此点对后续的影响，但同时我们也可以想出一个傻逼DP，f(i,j)代表前i个用了j张优惠券
然鹅1e14的数据迫使我们放弃了
然后我们发现只能使用带后悔的贪心
后悔又是个什么操作呢？？？我也不知道就是先把优惠券全败光用在优惠价前k小的牛上面，再在（k+1，n）区间上将每个差值放进小根堆就好了
上代码

#include<bits/stdc++.h>//聪明的头文件 
#define ll long long
#define fill(a,b) memset(a,b,sizeof(a))//机智的转换 
using namespace std;
const long long inf=5e11+100;
ll n,k,m,ans,ch;
struct kk{int a,b;bool flag;}node[50010];//帅气的定义 
int cmp(kk A,kk B){return A.b<B.b;}
int cmp2(kk A,kk B){return A.a<B.a;}//有远见的规划 
priority_queue<ll,vector<ll >,greater<ll > > Q;
int main(){
    scanf("%lld%lld%lld",&n,&k,&m);
    for (int i=1;i<=n;i++){
        scanf("%lld%lld",&node[i].a,&node[i].b);
        Q.push(node[i].b);
    }//完美的读入 
    sort(node+1,node+1+n,cmp);
    for (ll i=1;i<=k;i++){
        m-=node[i].b;
        if (m>=0)ans++;
        else {printf("%d",ans);return 0;}
    }sort(node+1+k,node+1+n,cmp2);//灵活的判断
    /*先把k张优惠券用完*/
    for (int i=k+1;i<=n;i++){
        if(!Q.empty()) ch=inf;
        else ch=Q.top();
        if (ch+node[i].b<node[i].a){
            m-=Q.top()+node[i].b;Q.pop();
            Q.push(node[i].b-node[i].a);
        }//机警的察觉 
        else m-=node[i].a;//灵活地变通 
        if (m>=0) ans++;
        else {printf("%lld",ans);return 0;}
    }printf("%lld",ans);//战术输出 
    return 0;//优雅的收尾 
}

有人总喷我没得注释所以我把注释写上去了