CF1526C2 Potions

题目知识点：反悔贪心。

题意

给定 \(n\) 瓶药水，喝下药水 \(i\) 可以给生命增加 \(a_i\) ，现在要求你按照从 \(1\) 到 \(n\) 的顺序遍历所有的药水，且你有两种选择，喝或者不喝药水。问在保证中途生命值不会为负数时，你能够最多喝多少瓶药水。

思路

假设所有药水都没有负数权值，那么我们显然是喝掉所有的药水。

现在考虑权值为负数的药水。我们的目标是喝最多瓶药水，那么意味着负数权值的药水我们也是要喝的。但是，我们要保证，我们喝的这个序列里面，所有的前置和一定是非负的。那么，我们可以转化为：我们先喝我们遇到的药水，假设我们喝下的药水使得生命值低于 \(0\) 了，那么意味着我们需要在所有当前的选择中丢弃一些负数权值的药水，使得我们的生命值回到非负的状态。

这个过程可以用优先队列做，做法如同下面代码的实现，实际上这道题的知识点就是反悔贪心。我们贪心的是喝更多的药水，但是这样会导致出现错解，此时可以对自己目前的选择再一次贪心，将那些影响最大的药水贪心的扔掉，这样就可以满足中途生命值不会为负数时，能够喝更多的药水。

实现

#include "bits/stdc++.h"

using i64 = int64_t;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    
    int n;
    std::cin >> n;
    
    std::vector<i64> w(n);
    for (auto &item : w) std::cin >> item;

    i64 tot = 0;
    std::priority_queue<i64, std::vector<i64>, std::greater<>> heap;
    for (auto item : w) {
        tot += item;
        heap.emplace(item);
        while (tot < 0) {
            tot -= heap.top();
            heap.pop();
        }
    }

    std::cout << heap.size() << '\n';
}