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

news/2024/10/20 2:32: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 longusing 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;
}