「ABC339C」 Perfect Bus

题意

有一辆公交车，路上会在 \(N\) 个站点停靠，每个站点会有 \(A_i\) 个乘客上下车(正数表示上车，负数表示下车)。

请选择一个恰当的正整数作为起始时车上的人数，使得路途中乘客的人数总为非负数。然后输出最终车上的人数。

分析

从头到尾遍历一遍 \(A\) ，计算总和 \(s\) ，这是到达终点后人数的变化量。

在计算 \(s\) 时，若 \(s\) 为负数，那就说明在开始需要至少为 \(|s|\) 的人数与 \(s\) 抵消。可以再用一个 \(mn\) 记录最小的 \(s(s<0)\) ，在最后，\(|mn|\) 就是最小的起始人数。

Code

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n,a[200005],s,mn=0x3f,sta;
signed main(){
    cin>>n;
    for(ll i=1;i<=n;++i){
        cin>>a[i];
        s+=a[i];
        mn=min(mn,s);
        if(mn<0)sta=max(sta,abs(mn));
    }
    cout<<sta+s;
    return 0;
}