Codeforces Round 723 (Div. 2) C2. Potions (Hard Version)

题目链接：Problem - 1526C2 - Codeforces

题意：给定长度为n的数组，每个元素可选择要或者不要，初始值为0，要求在保证得到的值始终不为负的情况下，能选择的最多的个数。

（翻译有误，应该是始终不为0。）

首先我们可以想到如果是正数则可以直接加上去，那么负数如何选择呢？

当碰到负数时，如果加上这个负数，我们的值仍然是非负数，那么本着贪心的原则，能贪则贪，我们就选择这个。那么如果加上这个值是负数呢？这里就需要反悔贪心的原理。

反悔贪心也就是指我当前阶段觉得这个可以贪，那我就贪，但当我走到下一个阶段发现贪当前这个远胜于贪之前那个的时候就反悔，不再要之前贪的那个了，俗称“渣男”。

https://v.douyin.com/i8KK2jSW/（与本题无关，并非引流）。

对于这道题就是当我们遇上加上这个数是负数时，如果之前有比这个数更小的负数，我们就删去之前更小的那个负数，选择这个数。这里需要用到小根堆来存储我们贪的负数。

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 200010 ;
int n , res ;
int a[N] ;

signed main()
{
    cin >> n ;
    for(int i = 1 ; i <= n ; i ++) scanf("%lld",&a[i]) ;
    priority_queue<int,vector<int>,greater<int>> h ;
    int sum = 0 ;
    for(int i = 1 ; i <= n ; i ++)
    {
        if(sum + a[i] >= 0)
        {
            res ++ ;
            sum += a[i] ;
            if(a[i] < 0)
            {
                h.push(a[i]) ;
            }
        }
        else
        {
            if(h.size() && h.top() < a[i])
            {
                int t = h.top() ;
                h.pop() ;
                h.push(a[i]) ;
                sum += a[i] - t ;
            } 
        }
    }
    cout << res << endl ;
    return 0 ;
}