LuoguP3045 [USACO12FEB]牛券Cow Coupons

果然我贪心能力还是太差了

ZR讲过的原题我回来对做法没有一丁点印象

有时候有这样一种题目

每个数有两种不同的价值

你可以选择价值低的,也可能花费一些神秘能力去获得价值高的

这时候我们直接贪心就可能会出现这种情况

当前最后解不是全局最优解

一般这种时候有两节决策,

要么DP

要么尝试进行可反悔的贪心

我们先按照所有牛的优惠后的价格排序,开一个小根堆

将前\(k\)个用优惠劵去买,很明显这可能是错误的

我们就将优惠券买的每一头牛的\(p - c\)丢到堆中,

对于一头使用了优惠券的牛\(i\)和未使用优惠券的牛\(j\)

如果有
\[ c_i+p_j > c_j+p_i \]
那么说明把优惠券用到\(j\)上更优

那么我们就把后\(n - k\)头牛按照\(p\)排序

每次看一看反悔是否更优就好了

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#include<cmath>
#define LL long long
#define pii pair<LL,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 1e5 + 3;
priority_queue <pii,vector<pii>,greater<pii> > q;
LL n,m,k;int ans;
struct node{
    LL p;
    LL c;   
}a[N];
bool book[N];
LL sum,tot; 
inline bool cmp(node x,node y){
    return x.c < y.c;   
}
inline bool cmpp(node x,node y){
    return x.p < y.p;   
}
inline LL read(){
    LL v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;
        ch = getchar();
    }
    return v * c;
}
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,cmp);
    LL sum = 0;
    for(int i = 1;i <= k;++i){
        sum += a[i].c;
        if(sum > m){
            printf("%d\n",i - 1);
            return 0;   
        }
        q.push(mk(a[i].p - a[i].c,i));
    }
    ans = k;
    sort(a + k + 1,a + n + 1,cmpp); 
    for(int i = k + 1;i <= n;++i){
        pii x = q.top();
        if(a[x.se].c + a[i].p > a[x.se].p + a[i].c){
            ans++;
            sum = sum - a[x.se].c;
            sum = sum + a[i].c + a[x.se].p;
            q.pop();
            q.push(mk(a[i].p - a[i].c,i));
        }
        else{
            ans++;
            sum += a[i].p;  
        }
        if(sum > m) {printf("%d\n",ans - 1);return 0;}
    }
    printf("%lld\n",n);
    return 0;
}