Readme

2599.Make-the-Prefix-Sum-Non-negative

本题是典型的反悔贪心。

我们一路维护前缀和sum。假设遇到当前的元素x，那么分一下几种情况。

场景1，如果x是正数，那么无脑收录。

场景2，如果x是负数，并且sum+x>=0，那么我们也会贪心地将其收入前缀，从而减少一次扔元素的操作。

场景3，就是如果x是负数，且sum+x<0，那么我们别我他法，必须将x扔走。但是将x扔走的同时，能捞一些什么好处呢？假设之前有某个负数y没有被扔走而是收录进了前缀，并且绝对值的y大于x，那么显然将y扔走比将x扔走更合算，并且将y扔走可以保证可以将x顺利保留在前缀里。

所以我们需要将场景2里所有收录过的负数，按照绝对值大小放入一个PQ。当遇到场景3的时候，我们将PQ里的最大值代替x去扔掉（如果大于x的话），这样同样用一次操作，可以获取最大的收益（尽可能地提升前缀和）。