本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-11-28 11:57:37

题目链接

题意

从一个长度为 $n$ 的序列中选出任意个，使这个序列的和非负，求这个序列的长度

解题思路

输入，如果这个数就是非负整数，那么就加上这个数，否则就判断加上这个数是否为负数，如果不是负数，就将序列之和加上这个数，否则如果之前选的数比现在选这个数损失大，那么就把损失大的改成这个数。

AC Code

废话少说，上代码：

#include <bits\/stdc++.h>\/\/万能头
using namespace std;
#define ll long long
inline int read() {\/\/快读模板 
    register char k = getchar();
    register int x = 0 , flg = 1;
    while (k < '0' || k > '9') {
        if (k == '-')flg = -1;
        k = getchar();
    }
    while (k >= '0' && k <= '9') {
        x = x * 10 + k - '0';
        k = getchar();
    }
    return x * flg;
}
inline void print(ll num) {\/\/快输模板 
    if (num < 0)putchar('-') , num = -num;
    if (num > 9)print(num \/ 10);
    putchar(num % 10 + '0');
} 
int n;\/\/有n个数 
int main() {
    n = read();
    priority_queue <int> q;\/\/默认大根堆 
    ll sum = 0 , ans = 0;\/\/sum是当前序列的和，ans是序列的长度 
    for (int i = 1 , a; i <= n; ++ i) {\/\/循环 
        a = read();\/\/输入 
        if (a >= 0) ++ans , sum += a;\/\/如果当前这个数本来就是非负的，那么就加上这个数，序列长度加一 
        else {
            if (abs(a) <= sum) {\/\/如果当前的和加上a还是非负的， 那么就加上这个数，序列长度加一 
                sum -= abs(a);\/\/减去个数 
                q.push(abs(a));\/\/加入大根堆 
                ++ ans;\/\/序列长度加一 
            }else {
                if (!q.empty() && q.top() > abs(a)) {\/\/如果大根堆非空且之前选的数比这个负数小，就改成这个数 
                    ll f = q.top();q.pop(); 
                    sum += f - abs(a);\/\/换，因为是覆盖掉之前选的数，所以序列长度不加 
                    q.push(abs(a));\/\/把当前更好的方案入堆 
                }
            }
        }
    }
    print(ans);\/\/输出序列长度 
    return 0;
}

如果有哪里有错请大佬指出。