当前位置: 首页 > 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;现在要对这些物体进行总结 类…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...