当前位置: 首页 > news >正文

ZCMU--5012: 铺设道路(差分思路)

Description

春春是一名道路工程师,负责铺设一条长度为 n 的道路。

铺设道路的主要工作是填平下陷的地表。

整段道路可以看作是 n 块首尾相连的区域,一开始,第 i 块区域下陷的深度为 di。 

春春每天可以选择一段连续区间 [L,R],填充这段区间中的每块区域,让其下陷深度减少 1。

在选择区间时,需要保证,区间内的每块区域在填充前下陷深度均不为 0。 

春春希望你能帮他设计一种方案,可以在最短的时间内将整段道路的下陷深度都变为 0。

Input

输入文件包含两行,第一行包含一个整数 n,表示道路的长度。 

第二行包含 n 个整数,相邻两数间用一个空格隔开,第 i 个整数为 di 。

Output

输出文件仅包含一个整数,即最少需要多少天才能完成任务。

数据范围

1≤n≤10^5,0≤di≤10000

Sample Input

6
4 3 2 5 3 5

Sample Output

9

解析:我们可以想成每次让某个区间都减1,然后使得整个序列都变成0,针对于区间都减1,很容易想到差分,转为差分数组之后,问题就变成了每次选择一个数+1或者-1,或者选择两个数分别-1,+1,问最少多少次使得全部数变成0,贪心优先选两个数的方式,选一个正数-1,选一个负数+1,然后最后只剩下正数或者负数,次数再加上他的大小即可,其实最后可以发现如果正数和为x,负数和为y,那么次数就是max(x,y)🙌。

#include <stdio.h>
#include <algorithm>
using namespace std;
const int N=1e+5;
int a[N],b[N];//b为差分数组
int main()
{int n,x=0,y=0;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1];//差分for(int i=1;i<=n;i++){if(b[i]>0) x+=b[i];//累加正数else y-=b[i];//累加负数}	printf("%d\n",max(x,y));return 0;
}

相关文章:

ZCMU--5012: 铺设道路(差分思路)

Description 春春是一名道路工程师&#xff0c;负责铺设一条长度为 n 的道路。 铺设道路的主要工作是填平下陷的地表。 整段道路可以看作是 n 块首尾相连的区域&#xff0c;一开始&#xff0c;第 i 块区域下陷的深度为 di。  春春每天可以选择一段连续区间 [L,R]&…...

算法模板总结(自用)

算法模板总结滑动窗口双指针算法数组相关合并两个有序数组左右指针技巧快慢指针技巧字符串相关左右指针反转字符串问题快慢指针替换空格字符问题链表相关快慢双指针删除链表的倒数第N个节点链表相交环形链表链表操作几数之和两数之和四个数组的四数之和三数之和同一数组中四数之…...

【架构师】零基础到精通——架构发展

博客昵称&#xff1a;架构师Cool 最喜欢的座右铭&#xff1a;一以贯之的努力&#xff0c;不得懈怠的人生。 作者简介&#xff1a;一名Coder&#xff0c;软件设计师/鸿蒙高级工程师认证&#xff0c;在备战高级架构师/系统分析师&#xff0c;欢迎关注小弟&#xff01; 博主小留言…...

C++(20):三路比较运算符

C20增加了三路比较运算符<>&#xff08;戏称航天飞机运算符&#xff09;&#xff0c;用于对类的比较运算符进行统一的设计。有两种使用方式&#xff1a;默认比较对于某些类&#xff0c;如果按照其成员逐一比较即可决定比较运算符的值&#xff0c;那么可以使用默认的三路运…...

MySQL workbench 字符集、字符序的概念与联系

在数据的存储上&#xff0c;MySQL提供了不同的字符集支持。而在数据的对比操作上&#xff0c;则提供了不同的字符序支持。 MySQL提供了不同级别的设置&#xff0c;包括server级、database级、table级、column级&#xff0c;可以提供非常精准的设置。 什么是字符集、字符序&am…...

DBA之路---数据库启动与关闭过程

DBA之路—数据库启动与关闭过程 1、启动过程 oracle启动的四个状态 shutdown、就是数据库关闭状态。 nomount模式 #启动instance &#xff0c;读取参数文件、分配sga空间启动后台进程&#xff0c;打开alter日志和其他trace文件startup nomount #该模式下只会创建实例并不加…...

Shell文件包含

和其他语言一样&#xff0c;Shell 也可以包含外部脚本。这样可以很方便的封装一些公用的代码作为一个独立的文件。 一、语法格式 Shell 文件包含的语法格式如下&#xff1a; . filename # 注意点号(.)和文件名中间有一空格 或 source filename 在当前bash环境下读取并执行file…...

计算机网络(六): HTTP,HTTPS,DNS,网页解析全过程

文章目录一、HTTP头部包含的信息通用头部请求头部响应头部实体头部二、Keep-Alive和非Keep-Alive的区别三、HTTP的方法四、HTTP和HTTPS建立连接的过程4.1 HTTP4.2 HTTPS五、HTTP和HTTPS的区别六、HTTPS的加密方式七、cookie和sessionsessioncookie八、HTTP状态码状态码200&…...

Android仿京东金融的数值滚动尺功能

自定义数值滚动尺,这个用的还是挺多的&#xff0c;例如京东金融的通过滚动尺选择金额等,而这次就是高仿京东金融的数值滚动尺。首先看看下效果图&#xff0c;如下&#xff1a;首先先给你们各个变量的含义&#xff0c;以免在后面的讲解中不知变量的意思&#xff0c;代码如下://最…...

Nginx 和 Tomcat 实现负载均衡

Nginx 和 tomcat 实现负载均衡 &#x1f3c6;荣誉认证&#xff1a;51CTO博客专家博主、TOP红人、明日之星&#xff1b;阿里云开发者社区专家博主、技术博主、星级博主。 &#x1f4bb;微信公众号&#xff1a;微笑的段嘉许 &#x1f4cc;本文由微笑的段嘉许原创&#xff01; &am…...

【万能排序之qsort、b_sort 、s_sort】

文章目录前言:star:qsort函数函数参数qsort函数的使用:star:模拟实现万冒泡排序函数参数模拟实现b_sort注意点:star:模拟实现万能选择排序函数参数模拟实现s_sort最后前言 我们所熟悉的冒泡排序&#xff0c;选择排序&#xff0c;插入排序&#xff0c;二分排序等都是基于给定的一…...

利用InceptionV3实现图像分类

最近在做一个机审的项目&#xff0c;初步希望实现图像的四分类&#xff0c;即&#xff1a;正常&#xff08;neutral&#xff09;、涉政&#xff08;political&#xff09;、涉黄&#xff08;porn&#xff09;、涉恐&#xff08;terrorism&#xff09;。有朋友给推荐了个github上…...

【Java】CAS锁

一、什么是CAS机制&#xff08;compare and swap&#xff09; 1.概述 CAS的全称为Compare-And-Swap&#xff0c;直译就是对比交换。是一条CPU的原子指令&#xff0c;其作用是让CPU先进行比较两个值是否相等&#xff0c;然后原子地更新某个位置的值。经过调查发现&#xff0c;…...

Linux服务器配置系统安全加固方法

1. SSH空闲超时时间建议为: 600-900 解决方案: 在【/etc/ssh/sshd_config】文件中设置【ClientAliveInterval】设置为600到900之间 vim /etc/ssh/sshd_config #将 ClientAliveInterval 参数值设置为 900 2. 修改检查SSH密码修改最小间隔 解决方案: 在【/etc/login.defs】文件…...

Codeforces Round #850 (Div. 2, based on VK Cup 2022 - Final Round)(A~E)

t宝酱紫喜欢出这种分类讨论的题&#xff1f;&#xff01;A1. Non-alternating Deck (easy version)给出n张牌&#xff0c;按照题目给的顺序分给两人&#xff0c;问最后两人手中各有几张牌。思路&#xff1a;模拟。AC Code&#xff1a;#include <bits/stdc.h>typedef long…...

qt源码--信号槽

本篇主要从Qt信号槽的连接、断开、调用、对象释放等方面展开&#xff1b; 1.信号建立连接过程 connect有多个重载函数&#xff0c;主要是为了方便使用者&#xff0c;比较常用的有2种方式&#xff1a; a. QObject::connect(&timer, &QTimer::timeout, &loop, &am…...

RecycleView详解

listview缓存请看: listview优化和详解RecycleView 和 ListView对比&#xff1a;使用方法上ListView&#xff1a;继承重写 BaseAdapter&#xff0c;自定义 ViewHolder 与 converView优化。RecyclerView: 继承重写 RecyclerView.Adapter 与 RecyclerView.ViewHolder。设置 Layou…...

【算法】最短路算法

&#x1f600;大家好&#xff0c;我是白晨&#xff0c;一个不是很能熬夜&#x1f62b;&#xff0c;但是也想日更的人✈。如果喜欢这篇文章&#xff0c;点个赞&#x1f44d;&#xff0c;关注一下&#x1f440;白晨吧&#xff01;你的支持就是我最大的动力&#xff01;&#x1f4…...

< Linux > 进程间通信

目录 1、进程间通信介绍 进程间通信的概念 进程间通信的本质 进程间通信的分类 2、管道 2.1、什么是管道 2.2、匿名管道 匿名管道的原理 pipe函数 匿名管道使用步骤 2.3、管道的读写规则 2.4、管道的特点 2.5、命名管道 命名管道的原理 使用命令创建命名管道 mkfifo创建命名管…...

学习 Python 之 Pygame 开发魂斗罗(二)

学习 Python 之 Pygame 开发魂斗罗&#xff08;二&#xff09;魂斗罗的需求开始编写魂斗罗1. 搭建主类框架2. 设置游戏运行遍历和创建窗口3. 获取窗口中的事件4. 创建角色5. 完成角色更新函数魂斗罗的需求 魂斗罗游戏中包含很多个物体&#xff0c;现在要对这些物体进行总结 类…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...