[ABC339C] Perfect Bus

Genius_Star · 2024-02-04 09:10:30 · 题解

思路：

要求最小值，且公交车上不能有负数个人，考虑贪心。

我们先假设初始有 0 人，找到公交车每时每刻人数的最小值即记为 Min；如果 Min<0，则这个时刻公交车上有 Min 人，因为是负数了，所以初始应该至少有 Min 人，才能导致现在不为负数个人；否则初始公交车上可以有 0 人。

时间复杂度为 O(N)。

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const ll N=200200;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
      write(x/10);
    putchar(x%10+'0');
}
ll n,sum,Min=0;
ll a[N];
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        sum+=a[i];
        Min=min(Min,sum);
    }
    if(Min<0)
      write(abs(Min)+sum);
    else
      write(sum);
    return 0;
}