Atcoder ABC339 C - Perfect Bus

Perfect Bus(完美的公交车)

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

【原题地址】

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

点击此处跳转至原题

【问题描述】

在这里插入图片描述

【输入格式】

在这里插入图片描述
在这里插入图片描述

【输出格式】

在这里插入图片描述

【样例1】

【样例输入1】

4
3 -5 7 -4

【样例输出1】

3

【样例说明1】

在这里插入图片描述

【样例2】

【样例输入2】

5
0 0 0 0 0

【样例输出2】

0

【解题思路】

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

本题是求最终车上的最少人数,因为车上人数不可能为负数,所以变量存在于发车时车上原有人数,条件允许的情况下原有人数为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();
	}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/389925.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

排序算法---计数排序

原创不易&#xff0c;转载请注明出处。欢迎点赞收藏~ 计数排序&#xff08;Counting Sort&#xff09;是一种线性时间复杂度的排序算法&#xff0c;其核心思想是通过统计待排序元素的个数来确定元素的相对位置&#xff0c;从而实现排序。 具体的计数排序算法步骤如下&#xff…

Netty Review - 直接内存的应用及源码分析

文章目录 Pre概述应用访问效率&#xff1a; 堆内存 VS 直接内存申请效率&#xff1a; 堆内存 VS 直接内存数据存储结构&#xff1a; 堆内存 VS 直接内存结论 ByteBuffer.allocateDirect 源码分析unsafe.allocateMemory(size) ---> C方法 JVM参数 -XX:MaxDirectMemorySize直接…

视觉slam十四讲学习笔记(五)非线性优化

已经知道&#xff0c;方程中的位姿可以由变换矩阵来描述&#xff0c;然后用李代数进行优化。观测方程由相机成像模型给出&#xff0c;其中内参是随相机固定的&#xff0c;而外参则是相机的位姿。 目录 前言 一、状态估计问题 1 最大后验与最大似然 2 最小二乘的引出 二、非…

JavaScript中null和undefined的区别

JavaScript中null和undefined是两个特殊的值&#xff0c;经常在编程中遇到。虽然它们经常被混淆&#xff0c;但它们有着不同的含义和用法。本文将详细介绍JavaScript中null和undefined的区别&#xff0c;帮助开发者更好地理解和使用它们。 首先&#xff0c;让我们来了解一下nu…

css篇---移动端适配的方案有哪几种

移动端适配 移动端适配是指同一个页面可以在不同的移动端设备上都有合理的布局。主流实现的方案有 响应式布局通过rem或者vw,vh 等实现不同设备有相同的比例而实现适配 首先需要了解viewport 【视口】 视口代表了一个可看见的多边形区域&#xff08;通常来说是矩形&#xff0…

函数递归与迭代附n的阶乘+顺序打印一个整数的每一位数+求第n个斐波那契数

1. 什么是递归&#xff1f; 递归其实是一种解决问题的方法&#xff0c;在C语言中&#xff0c;递归就是函数自己调用自己。 下面是一个最简单的C语言递归代码&#xff1a; #include <stdio.h> int main() {printf("hehe\n");main();//main函数中⼜调⽤了main函数…

BBC英式口语~发音练习~笔记整理

参考资料 原视频地址&#xff1a; https://www.bilibili.com/video/BV1D7411n7bS/?spm_id_from333.1245.0.0&vd_source5986fc7c8e6d754f3ca44233573aeaff 笔记图片

2.11题目

#include <stdio.h> int main() { char a; while((a getchar()) ! -1) { if(a > A && a < Z) a32; putchar(ch); } return 0;} ———————————————— 版权声明&#xff1a;本文为博主原创文章…

阿里云/腾讯云幻兽帕鲁服务器据点最大帕鲁工作数量最多15个,改成20不生效?

例如&#xff0c;在阿里云的计算巢管理中&#xff0c;找到你的这台部署幻兽帕鲁的服务器实例&#xff0c;选择右上角的“修改游戏配置” 然后选择“基地内工作帕鲁的最大数量”改成20 有人说更改上面的数字&#xff0c;根本不起作用。原因可能如下&#xff1a; 参考资料&#…

css篇---分辨率物理像素和逻辑像素

物理分辨率和逻辑分辨率 物理分辨率是生产屏幕时就固定的&#xff0c;它是不可改变的 -----电脑像素 逻辑分辨率是由软件决定的 【电脑的设置中可以修改分辨率】----css像素 设备像素比 dpr同一方向上的物理像素/css像素 &#xff08;缩放比是1的情况&#xff09; 假设dpr4/…

网络安全最典型基础靶场-DVWA-本地搭建与初始化

写在前面&#xff1a; 之前也打过这个 DVWA 靶场&#xff0c;但是是在虚拟机环境下的一个小块分区靶场&#xff1b; 本篇博客主要介绍在本地搭建 DVWA 靶场以及靶场的初始化&#xff0c;后续会陆续更新通关教程。 由于我们是在本地搭建&#xff0c;则需要基于你已经装好 phpstu…

cefsharp121(cef121.3.7Chromium121.0.6167.160)升级测试及其他H264版本

一、版本说明 1.1 本此版本 此版本CEF 121.3.7+g82c7c57+chromium-121.0.6167.160 / Chromium 121.0.6167.160 1.2 其他支持H264版本 支持H264推荐版本:V100,V109,V111,V119版本,其他V114,V115,V108,V107 支持win7/win8/win8.1最后版本v109.x 支持NET4.5.2最后版本v114.x …

一览大模型长文本能力

前言 如今的大模型被应用在各个场景&#xff0c;其中有些场景则需要模型能够支持处理较长文本的能力(比如8k甚至更长)&#xff0c;其中已经有很多开源或者闭源模型具备该能力比如GPT4、Baichuan2-192K等等。 那关于LLM的长文本能力&#xff0c;目前业界通常都是怎么做的&…

STM32 寄存器操作 GPIO 与下降沿中断

一、如何使用stm32寄存器点灯&#xff1f; 1.1 寄存器映射表 寄存器本质就是一个开关&#xff0c;当我们把芯片寄存器配置指定的状态时即可使用芯片的硬件能力。 寄存器映射表则是开关的地址说明。对于我们希望点亮 GPIO_B 的一个灯来说&#xff0c;需要关注以下的两个寄存器…

leetcode hot100不同路径

本题可以采用动态规划来解决。还是按照五部曲来做 确定dp数组&#xff1a;dp[i][j]表示走到&#xff08;i&#xff0c;j&#xff09;有多少种路径 确定递推公式&#xff1a;我们这里&#xff0c;只有两个移动方向&#xff0c;比如说我移动到&#xff08;i&#xff0c;j&#x…

【机器学习】数据清洗之识别重复点

&#x1f388;个人主页&#xff1a;甜美的江 &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;机器学习 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、交流进步…

React入门到精通:掌握前端开发的必备技能!

介绍&#xff1a;React是一个由Facebook开发和维护的JavaScript库&#xff0c;用于构建用户界面&#xff0c;特别是用于构建单页应用程序和移动应用程序的用户界面。以下是对React的详细介绍&#xff1a; 虚拟DOM&#xff1a;React通过使用虚拟DOM&#xff08;Document Object …

Rust 数据结构与算法:3栈:用栈实现符号匹配

1、符号匹配 如&#xff1a; (56)(78)/(43)、{ { ( [ ] [ ])}}、(ab)(c*d)func() 等各类语句的符号匹配。 这里我们关注的不是数字而是括号&#xff0c;因为括号更改了操作优先级&#xff0c;限定了语言的语义&#xff0c;这是非常重要的。如果括号不完整&#xff0c;那么整个…

C语言指针(初阶)

文章目录 1:内存与地址1.1内存1.2:如何理解编址 2:指针变量与地址2.1:指针变量与解引用操作符2.1.1:指针变量2.1.2:如何拆解指针类型2.1.3:解引用操作符 2.2:指针变量的大小 3:指针变量类型的意义代码1解引用修改前解引用修改后 代码2解引用修改前解引用修改后 4:const修饰指针…

RSIC-V“一芯”学习笔记(三)——读后感以及部分PA0工作

文章目录 一、别像弱智一样提问二、提问的智慧三、安装linux以及配置问题3.1 关于问题配置 一、别像弱智一样提问 提问前&#xff0c;应该清晰问自己几个问题&#xff0c;1. 是否尝试了在搜索引擎进行搜索过2. 相关的手册和文档是否看了3. 找找有没有常见的问题文档&#xff0…