能量获取

【题意简述】

初始能量为 $h$，依次经过 $n$ 份能量变化为 $a_i$ 的样本。每份样本可以获取或跳过，且每次获取后能量不能小于 $0$。求最多获取多少份样本。

【Hint】

【提示】

暂时获取当前样本。若能量变为负数，就从已经获取的样本中删除能量变化最小的一份。

【数据点 1∼51\sim 51∼5】

枚举最终选择的样本集合，再按原顺序模拟。时间复杂度为 $\mathcal{O}(2^n n)$。

【数据点 6∼106\sim 106∼10】

定义 $f_j$ 表示处理完当前前缀后，恰好获取 $j$ 份样本时能够保留的最大能量。不可达状态记为负无穷，初始时 $f_0=h$。处理 $a_i$ 时倒序枚举 $j$，若 $f_{j-1}+a_i\geq 0$，则

对于相同的获取次数，保留能量更大的方案一定不劣。时间复杂度为 $\mathcal{O}(n^2)$，空间复杂度为 $\mathcal{O}(n)$。

【数据点 11∼1511\sim 1511∼15】

特殊性质保证非负数全部位于负数之前。先获取全部非负样本，再把负数从大到小排序，依次获取到无法继续即可。这个做法说明：选择数量相同时，应当删去最消耗能量的样本。

【正解】

从左到右处理样本，并暂时把每一份样本都加入当前方案。用小根堆保存已加入样本的 $a_i$，用 $S$ 保存当前能量。

若加入 $a_i$ 后 $S<0$，当前选择无法全部保留。为了使选择数量只减少 $1$ 且剩余能量最大，应当删除堆中的最小值。因为加入前的能量非负，而最小值不大于刚加入的 $a_i$，删除一次一定足以恢复 $S\geq 0$。

处理完任意前缀后，堆中保存一个合法方案；并且在选择数量相同的所有合法方案中，它的剩余能量最大。若当前前缀无需删除，直接加入不会破坏这一性质；若必须删除一个数，删除最小值使剩余能量最大，同样不会影响后续最优选择。因此最终堆的大小就是答案。

【复杂度分析】

时间复杂度为 $\mathcal{O}(n\log n)$，空间复杂度为 $\mathcal{O}(n)$。能量累加需要使用 long long。

【参考代码】

1#include <bits/stdc++.h>2using namespace std;3 4int main() {5    ios::sync_with_stdio(false);6    cin.tie(nullptr);7 8    int c, T;9    if (!(cin >> c >> T)) return 0;10    while (T--) {11        int n;12        long long h;13        cin >> n >> h;14        priority_queue<long long, vector<long long>, greater<long long> > Heap;15        long long Energy = h;16        for (int i = 1; i <= n; ++i) {17            long long Value;18            cin >> Value;19            Energy += Value;20            Heap.push(Value);21            if (Energy < 0) {22                Energy -= Heap.top();23                Heap.pop();24            }25        }26        cout << Heap.size() << '\n';27    }28    return 0;29}