题目链接
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;
}
