题解归档 - cf2224A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2224A
• 本地来源：problems/cf2224A/idea.md
• 题目链接：https://codeforces.com/contest/2224/problem/A
• 原始标题：cf2224A - Zhily and Array Operating

思路

cf2224A - Zhily and Array Operating

Pattern

Process the array from right to left. After all useful operations to the right
are done, index i has only two meaningful choices:

• do not choose i: final value is a[i];
• choose i: final value is a[i] + final[i+1].

Claim

If final[i+1] > 0, choosing i is always at least as good as not choosing it:
it increases final[i], cannot reduce the number of positives in the suffix,
and only helps positions further left.

If final[i+1] <= 0, choosing i only decreases or preserves final[i], so it
is never better than not choosing it.

Therefore the greedy rule is:

final[i] = a[i] + max(0, final[i+1]).

Count how many final[i] are positive.

Complexity

O(n) per test case, O(n) memory.

代码

来源：problems/cf2224A/solution.cpp

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

using ll=long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        vector<ll>a(n);
        for(ll &x:a) cin>>x;
        ll cur=a.back();
        int ans=cur>0;
        for(int i=n-2;i>=0;i--){
            if(cur>0) cur+=a[i];
            else cur=a[i];
            if(cur>0) ans++;
        }
        cout<<ans<<"\n";
    }
    return 0;
}