Atcoder ABC339 C - Perfect Bus

2024-02-14 23:36

文章标签 bus atcoder perfect abc339

本文主要是介绍Atcoder ABC339 C - Perfect Bus，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Perfect Bus（完美的公交车）

时间限制：2s 内存限制：1024MB

【原题地址】

所有图片源自Atcoder，题目译文源自脚本Atcoder Better!

点击此处跳转至原题

【问题描述】

在这里插入图片描述

【输入格式】

在这里插入图片描述

【输出格式】

在这里插入图片描述

【样例1】

【样例输入1】

4
3 -5 7 -4

【样例输出1】

【样例说明1】

在这里插入图片描述

【样例2】

【样例输入2】

5
0 0 0 0 0

【样例输出2】

【解题思路】

老汉使用到的是贪心的解题方式

本题是求最终车上的最少人数，因为车上人数不可能为负数，所以变量存在于发车时车上原有人数，条件允许的情况下原有人数为0时肯定是最小值，但是为了满足不为负这个条件，我们需要通过一个合适的原有人数进行维护。
用一个变量sum存储每个阶段车上对比原发车时的人数变化量，变量min用于存储其中变化量最低的值，当处于这个阶段都满足不为负数时，其他阶段也必然满足，最后根据sum和min求得最终答案。

代码注释有详细过程

【代码】

package ABC339_C_PerfectBus;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();long[] a = new long[n + 1];// 获取人流变化的总和，即最终总变化量long sum = 0;// 存放人流变化量总和最小阶段的值long min = Long.MAX_VALUE;for (int i = 1; i <= n; i++) {a[i] = scan.nextLong();sum += a[i];// 获取最小值min = Math.min(min, sum);}// 当最小阶段值为负数时，则代表开始时车上最少要有-min人if (min < 0) {System.out.println(sum - min);} else {// 不为负数时，代表开始时车上最少0人System.out.println(sum);}scan.close();}
}