小Why的简单加减

思路

计算前缀和，先看是否存在前缀和小于0的位置。

如果存在，说明我们至少需要放弃一个点。

则从这前缀中，找出最小下标，标记为无穷小（这个点，可以做为后边其他负数点的左边界。）

接下来就清晰了。

由于操作数有限，从所有的负数点中，贪心地取最小的，即可。

代码

源自

#include<bits/stdc++.h>
using namespace std;

#define endl '\n';
typedef long long LL;

void solve(){
    LL n,k,res = 0;
    cin >> n >> k;
    vector<LL> a(n + 1),s(n + 1);
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
        res += (a[i] >= 0);
    }
    int pos = -1;
    for(pos = 1;pos <= n;pos++){
        if(s[pos] < 0){
            pos = min_element(a.begin() + 1,a.begin() + pos + 1) - a.begin();
            a[pos] = -1e18;
            break;
        }
    }
    vector<LL> b;
    for(int i = 1;i <= n;i++){
        if(a[i] < 0)b.push_back(-a[i]);
    }
    sort(b.begin(),b.end());
    for(int i = 0;i < b.size();i++){
        if(k - b[i] >= 0){
            k -= b[i];
            res++;
        }
        else break;
    }
    cout << res << endl;

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }

    return 0;
}