Codeforces - 1526C1＆＆C2 - Potions

Codeforces - C1&&C2 - Potions

There are n potions in a line, with potion 1 on the far left and potion n on the far right. Each potion will increase your health by ai when drunk. ai can be negative, meaning that potion will decrease will health.

You start with 0 health and you will walk from left to right, from first potion to the last one. At each potion, you may choose to drink it or ignore it. You must ensure that your health is always non-negative.

What is the largest number of potions you can drink?

Input

The first line contains a single integer n (1≤n≤200000) — the number of potions.

The next line contains n integers a1, a2, … ,an (−10^9≤ai≤109) which represent the change in health after drinking that potion.

Output

Output a single integer, the maximum number of potions you can drink without your health becoming negative.

Example

input

6
4 -4 1 -3 1 -3

output

5

问题解析

这题是说有n瓶药，吃了之后会恢复a[i]点生命值或减少a[i]点生命值，你从左往右按顺序吃（也可以选择不吃），问你在生命值不为负的情况下能吃几瓶药。

因为c1和c2仅有数据大小的差异，我就直接按照c2来写，这题可以直接贪心写，把那些小的药水都忽略掉即可。

我们可以准备一个小根堆，从左往右将药剂插入小根堆中，当小根堆总和为负了，就把它最小的元素弹出，直到总和不为负为止，在此过程中维护一下吃下药水数的最大值即可。每次插入和弹出都是logn，所以总复杂度才nlogn。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;
int n, m;


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;

    int n;
    cin >> n;
    vector<int>v(n);
    priority_queue<int,vector<int>,greater<int>>que;
    int res = 0,ans=0;
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        que.push(v[i]);
        res += v[i];
        while (res < 0)
        {
            res -= que.top();
            que.pop();
        }
        ans = max(ans, (ll)que.size());
    }
    cout << ans << endl;
    return 0;
}