Codeforces Round 946 (Div. 3) G. Money Buys Less Happiness Now（反悔贪心）
题目链接
Codeforces Round 946 (Div. 3) G. Money Buys Less Happiness Now
思路
我们维护当前拥有的钱 s u m sum sum和一个大根堆，大根堆记录用了哪些 c i c_{i} ci。
我们先尝试获得当前月的幸福， s u m = s u m − c i sum = sum - c_{i} sum=sum−ci，并将 c i c_{i} ci扔到大根堆里。如果当前的 s u m < 0 sum < 0 sum<0，则需要进行反悔操作。从大根堆里面取出最大的 c k c_{k} ck，令 s u m = s u m + c k sum = sum + c_{k} sum=sum+ck即可。
在每个月的月末，我们让 s u m = s u m + x sum = sum + x sum=sum+x。
最终的答案即为大根堆中 c i c_{i} ci的数量。
时间复杂度： O ( m l o g m ) O(mlogm) O(mlogm)
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 2e5 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;
int m, x;
int c[N];
void solve()
{
cin >> m >> x;
for (int i = 1; i <= m; i++)
{
cin >> c[i];
}
priority_queue<int, vector<int>, less<int>>q;
int sum = x;
for (int i = 2; i <= m; i++)
{
sum -= c[i];
q.push(c[i]);
if (sum < 0)
{
sum += q.top();
q.pop();
}
sum += x;
}
cout << q.size() << 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;
}