洛谷P3045 [USACO12FEB] Cow Coupons G（堆，反悔贪心）

题目链接

https://www.luogu.com.cn/problem/P3045

思路

我们先贪心地使用$k$个最小的优惠假，再考虑如何反悔。

假设$sum$表示现在用了多少钱，$i$表示一个已经使用了优惠卷的物品，$j$表示一个未购买的物品。

如果用原价购买$j$，则需要用：$sum+p_j$。

如果用优惠假购买$j$，则需要用：$sum-c_i+p_i+c_j$。

如果要换成用原价购买$i$，用优惠价购买$j$，则需要满足：$sum-c_i+p_i+c_j<sum+p_j$，化简得到：$p_i-c_i<p_j-c_j$。换句话说，就是物品$i$用优惠卷节省的钱要$<$物品$j$用优惠卷节省的钱。

这里，每一个物品用优惠卷节省的钱可以使用优先队列$delta$来维护。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e4 + 5;
int n, k, m;
int p[N], c[N];
bool st[N];
priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>P, C;
priority_queue<int, vector<int>, greater<int>>delta;
void solve()
{
cin >> n >> k >> m;
for (int i = 1; i <= n; i++)
{
cin >> p[i] >> c[i];
P.push({p[i], i});
C.push({c[i], i});
}
//初始化k个，保证后面delta里面一定有k个值
for (int i = 1; i <= k; i++) delta.push(0);

int ans = 0;
while (P.size())
{
pair<int, int> px = P.top();
pair<int, int> cx = C.top();
//买过的就不考虑了
if (st[px.second])
{
P.pop();
continue;
}
if (st[cx.second])
{
C.pop();
continue;
}

//使用优惠卷的价格：delta.top() + cx.first
//原价：px.first
if (delta.top() + cx.first > px.first)
{
m -= px.first;
P.pop();
st[px.second] = true;
}
else
{
m -= (cx.first + delta.top());
delta.pop();
C.pop();
st[cx.second] = true;
delta.push({p[cx.second] - c[cx.second]});
}
if (m >= 0) ans++;
else break;
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int test = 1;
// cin >> test;
for (int i = 1; i <= test; i++)
{
solve();
}
return 0;
}

原文地址：https://blog.csdn.net/weixin_74754298/article/details/142590793

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！