CF 1526C2 Potions (Hard Version)

题目描述

http://codeforces.com/contest/1526/problem/C2

简要题意：给定一个长度为 $n$ 的序列 $a_i$，要求选出最长的一个子序列，满足这个子序列的任意前缀非负

$n\le 2\times 10^5$

Solution

注意到限制只有下界限制，所以所有非负数一定选，对于一个负数，能选则选，否则按照最传统的反悔贪心的做法即可

时间复杂度 $O(n\log n)$

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define maxn 200010
#define ll long long
#define INF 1000000000000000000
using namespace std;

int n, a[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    priority_queue<int> Q; ll sum = 0; int ans = 0; 
    for (int i = 1; i <= n; ++i) {
        if (a[i] >= 0) sum += a[i], ++ans;
        else {
            if (sum + a[i] >= 0) sum += a[i], ++ans, Q.push(-a[i]);
            else if (!Q.empty() && Q.top() > -a[i]) sum += Q.top() + a[i], Q.pop(), Q.push(-a[i]); 
        } 
    } cout << ans << "\n"; 
    return 0;
}