[ABC339C] Perfect Bus 题解

Sakura_11 · 2024-02-04 08:57:54 · 题解

说句闲话：

ABC 的 C 题好久没这么水了，赛时 AC。

题目大意：

公共汽车上的乘客人数始终是一个非负整数。

在第 i 站，乘客数量增加了 A_i。这里，A_i 可以是负数，表示乘客数量减少了 |A_i|。并且，除了在车站，没有乘客上下车。求最小可能的乘客数量。

分析：

题目给出了每个车站上下车的人数，求最后最小的乘客数量。采用贪心策略。由于每时每刻的人数都应该是非负数，我们每次循环加上 a_i，每当小于 0 时，就重新赋值为 0，否则继续加。

Code:

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e5 + 10;
LL a[N];
int main() {
    LL n; scanf("%lld", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &a[i]);
    LL ans = 0;
    for (int i = 1; i <= n; ++i) {
        if(ans + a[i] < 0) {
            ans = 0;
         //小于0就清0
        } else ans += a[i];
        //加上每次的上下车人数
    }
    printf("%lld", ans);
    return 0;
}