洛谷P3045 [USACO12FEB]Cow Coupons G 题解

题目链接：P3045 [USACO12FEB]Cow Coupons G

题意：

FJ 准备买一些新奶牛。市场上有 \(N\) 头奶牛，第 \(i\) 头奶牛价格为 \(P_i\)。FJ 有 \(K\) 张优惠券，使用优惠券购买第 \(i\) 头奶牛时价格会降为 \(C_i\)，当然每头奶牛只能使用一次优惠券。FJ 想知道花不超过 \(M\) 的钱最多可以买多少奶牛？

\(1 \le K \le N \le 5 \times 10^4,~1 \le C_i \le P_i \le 10^9,~1 \le M \le 10^{14}\)

这种贪心题还是比较经典的反悔型贪心。

首先我们先把上界算出来，也就是选 \(k\) 个最小的 \(C_i\) ，然后在剩下的 \(P_i\) 里选 \(n-k\) 个最小的。

考虑如何更新答案。我们实际上只有一种选择：原价买 \(x\) ，并把 \(x\) 用了的优惠券用于买新的

那么这个 \(x\) 怎么选合适呢？肯定优先选优惠力度小的啊！也就是 \(P_i-C_i\) 小的。

我们可以维护一个大根堆，在选 \(k\) 个最小的 \(C_i\) 时，把 \(C_i - P_i\) 塞进去。

然后再用两个小根堆，分别维护当前最便宜的 \(P_i\) 和 \(C_i\) ，然后选择就好了，详见代码

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e4 + 15))
#define Fi first
#define Se second

int n,m,k; char vis[N];
struct node { int p,c; } a[N];
priority_queue< int,vector<int>,greater<int> > q1;
priority_queue< pii,vector<pii>,greater<pii> > q2,q3;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> k >> m;
    for(int i = 1; i <= n; i++) cin >> a[i].p >> a[i].c;
    sort(a + 1, a + 1 + n, [](node a, node b) { return a.c < b.c; });
    int now = 0;
    for(int i = 1; i <= k; i++)
    {
        now += a[i].c; q1.push(a[i].p - a[i].c);
        if(now > m) { return cout << i - 1 << '\n', 0; }
    }
    if(k == n) { return cout << n << '\n', 0; }
    for(int i = k + 1; i <= n; i++) {
        q2.emplace(a[i].c, i); q3.emplace(a[i].p, i);
    }
    int res = k;
    for(int i = k + 1; i <= n; i++)
    {
        while(vis[q2.top().Se]) q2.pop();
        while(vis[q3.top().Se]) q3.pop();
        int p1 = q2.top().Se, p2 = q3.top().Se;
        int tmp1 = q2.top().Fi + q1.top(), tmp2 = q3.top().Fi;
        if(tmp1 < tmp2)
        {
            now += tmp1; q1.pop(); q2.pop();
            q1.push(a[p1].p - a[p1].c); vis[p1] = true;
        }else {
            now += tmp2; q3.pop(); vis[p2] = true;
        }
        ++res;
        if(now > m) { return cout << res - 1 << '\n', 0; }
    }
    cout << n << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/46396/solution-p3045