P3045 [USACO12FEB] Cow Coupons G （用堆实现反悔贪心）

medicos / 2024-10-29 / 原文

题解

题目链接

P3045 [USACO12FEB] Cow Coupons G

解题思路

反悔贪心
大体思路即为: 将所有 $p_i$ 与 $c_i$ 分别存入两个小根堆中，每次取出下标未使用过的堆顶元素 $p_i$ 与 $c_j$，并变成实际的应增加费用 $p_i$ 与 $c_j + \Delta k$ (最小的 $p_k - c_k$) 进行比较，决定选择 $i$ 还是 $j$ . 具体的思路与证明可以看Luogu题解, 里面非常详细与全面.

重点代码部分就是

if (tc + delta.top() > tp) {    //相当于将 对i使用优惠卷实际上应该增加的费用 和 不对j使用优惠卷应该增加的费用 作比较
            m -= tp;
            P.pop();
            vis[i] = 1;
        }
        else {
            m -= tc + delta.top();
            delta.pop();
            C.pop();
            vis[j] = 1;
            delta.push(p[j] - c[j]);
        }

这里Luogu的大部分题解写的都是移项后的 $delta.top() > tp - tc$, 困扰了我非常久:为什么tp和tc明明对应的下标不一定一样,却可以直接相减.

时间复杂度与空间复杂度分析

由于堆的使用, 两个最大大小为n和一个大小为k的堆,时间与空间复杂度均为 $O(nlogn)$ 左右.

完整代码

#include <bits/stdc++.h>

#define int long long

using namespace std;

using PII = pair<int, int>;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);

    int n, k, m;
    cin >> n >> k >> m;

    priority_queue<PII, vector<PII>, greater<>> P, C;
    priority_queue<int, vector<int>, greater<>> delta;

    vector<int> p(n + 1), c(n + 1), vis(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> p[i] >> c[i];
        P.push({p[i], i});
        C.push({c[i], i});
    }
    for (int i = 1; i <= k; ++i) delta.push(0);  //相当于给了k次无脑使用优惠卷的机会
    int ans = 0;
    while (P.size()) {
        auto [tp, i] = P.top();
        auto [tc, j] = C.top();
        if (vis[i]) {
            P.pop();
            continue;
        }
        if (vis[j]) {
            C.pop();
            continue;
        }
        if (tc + delta.top() > tp) {    //相当于将 对i使用优惠卷实际上应该增加的费用 和 不对j使用优惠卷应该增加的费用 作比较
            m -= tp;
            P.pop();
            vis[i] = 1;
        }
        else {
            m -= tc + delta.top();
            delta.pop();
            C.pop();
            vis[j] = 1;
            delta.push(p[j] - c[j]);
        }
        if (m >= 0) ans++;
        else break;
    }
    cout << ans << "\n";

    return 0;
}