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

【洛谷 P5019】[NOIP2018 提高组] 铺设道路 题解(分治算法+双指针)

[NOIP2018 提高组] 铺设道路

题目背景

NOIP2018 提高组 D1T1

题目描述

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

铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 n n n 块首尾相连的区域,一开始,第 i i i 块区域下陷的深度为 d i d_i di

春春每天可以选择一段连续区间 [ L , R ] [L,R] [L,R] ,填充这段区间中的每块区域,让其下陷深度减少 1 1 1。在选择区间时,需要保证,区间内的每块区域在填充前下陷深度均不为 0 0 0

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

输入格式

输入文件包含两行,第一行包含一个整数 n n n,表示道路的长度。 第二行包含 n n n 个整数,相邻两数间用一个空格隔开,第 i i i 个整数为 d i d_i di

输出格式

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

样例 #1

样例输入 #1

6   
4 3 2 5 3 5

样例输出 #1

9

提示

【样例解释】

一种可行的最佳方案是,依次选择:
[ 1 , 6 ] [1,6] [1,6] [ 1 , 6 ] [1,6] [1,6] [ 1 , 2 ] [1,2] [1,2] [ 1 , 1 ] [1,1] [1,1] [ 4 , 6 ] [4,6] [4,6] [ 4 , 4 ] [4,4] [4,4] [ 4 , 4 ] [4,4] [4,4] [ 6 , 6 ] [6,6] [6,6] [ 6 , 6 ] [6,6] [6,6]

【数据规模与约定】

对于 30 % 30\% 30% 的数据, 1 ≤ n ≤ 10 1 ≤ n ≤ 10 1n10
对于 70 % 70\% 70% 的数据, 1 ≤ n ≤ 1000 1 ≤ n ≤ 1000 1n1000
对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 100000 , 0 ≤ d i ≤ 10000 1 ≤ n ≤ 100000 , 0 ≤ d_i ≤ 10000 1n100000,0di10000


思路

使用分治算法,将道路分成多个区间。在每个区间里,寻找最小的元素,以该元素的位置为界又划分为左右两个新区间,同时 ans 加上这个最小的元素。不断对每个区间进行划分,直到无法继续划分下去为止。

注意:数据量较大,需要使用快读。


AC代码

#include <iostream>
#include <climits>
#include <algorithm>
#define AUTHOR "HEX9CF"
using namespace std;const int N = 1e6 + 7;int n;
int d[N];
int ans;void read(int &x)
{char ch = getchar();x = 0;while (!('0' <= ch && ch <= '9')){ch = getchar();}while (('0' <= ch && ch <= '9')){x = x * 10 + ch - '0';ch = getchar();}
}int sub(int low, int high) {int mini = INT_MAX;int pos = low;for(int i = low; i <= high; i++) {if(d[i] < mini) {mini = d[i];pos = i;}}for(int i = low; i <= high; i++) {d[i] -= mini;}ans += mini;return pos;
}void partition(int low, int high) {if(low > high) {return;}int pos = sub(low, high);partition(low, pos - 1);partition(pos + 1, high);// cout << low << " " << high << " " << pos << endl;
}int main()
{ans = 0;read(n);for (int i = 1; i <= n; i++){read(d[i]);}partition(1, n);printf("%d", ans);return 0;
}

相关文章:

【洛谷 P5019】[NOIP2018 提高组] 铺设道路 题解(分治算法+双指针)

[NOIP2018 提高组] 铺设道路 题目背景 NOIP2018 提高组 D1T1 题目描述 春春是一名道路工程师&#xff0c;负责铺设一条长度为 n n n 的道路。 铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 n n n 块首尾相连的区域&#xff0c;一开始&#xff0c;第 i i i …...

牛客刷题记录11.12

继承和组合 二进制数统计 1的个数 和 0 的个数...

NextJS开发:使用IconPark、Lucide图标库

IconPark、Lucide两个很不错的图标库&#xff0c;如果需要用到微信、阿里等国内logo可以使用IconPark&#xff0c;Lucide中没有包含这些内容。 安装IconPark npm install icon-park/react --save简单使用 import {Home} from icon-park/react;<Home/> <Home theme&…...

11.12总结

这一周主要写了个人中心的几个功能&#xff0c;资料修改&#xff0c;收货地址的创建和修改删除&#xff0c;还有主页界面和商品界面...

Gogs安装和部署教程-centos上

0、什么是 Gogs? Gogs 是一款极易搭建的自助 Git 服务。 Gogs 的目标是打造一个最简单、最快速和最轻松的方式搭建自助 Git 服务。使用 Go 语言开发使得 Gogs 能够通过独立的二进制分发&#xff0c;并且支持 Go 语言支持的 所有平台&#xff0c;包括 Linux、Mac OS X、Windo…...

Unity中Shader雾效的实现方法一

文章目录 前言一、在片元着色器中使用如下公式计算最终的颜色 lerp(雾效颜色&#xff0c;物体颜色&#xff0c;雾效混合因子)1、获取雾效颜色2、物体的颜色一般通过纹理采样得到&#xff0c;此处用 1 代替测试3、获取 雾效混合因子&#xff08;由 雾的距离 和 雾的浓度决定&am…...

Mac安装配置Tomcat,以及使用(详解)

目录 一、Tomcat下载&#xff1a; 1、左栏选择Tomcat版本 2、点击下载即可&#xff0c;任选其一 ​编辑3、下载好的文件夹放到用户名下即可&#xff08;之前已经下载过&#xff0c;这里以Tomcat 8.5.88为演示&#xff09;&#xff0c;这里提供8.5.88的安装包&#xff1a; 二…...

Smart Link 和 Monitor Link应用

定义 Smart Link常用于双上行链路组网&#xff0c;提高接入的可靠性。 Monitor Link通过监视上行接口&#xff0c;使下行接口同步上行接口状态&#xff0c;起到传递故障信息的作用。 Smart Link&#xff0c;又叫做备份链路。一个Smart Link由两个接口组成&#xff0c;其中一个…...

【debug】解决Kali虚拟机开机黑屏,左上角光标一直闪动无法开机问题

做网络攻防实验时&#xff0c;突然Kali无法打开&#xff0c;遇到这个问题。。。。。。 遇到的问题 突然kali虚拟机变成如下黑屏&#xff0c;无法开机&#xff0c;左上角光标闪动&#xff0c;重启无效。 解决办法 在上图界面&#xff0c;按Ctrl F3&#xff08;不同电脑快捷键…...

目标检测YOLO实战应用案例100讲-基于改进YOLO算法的道路交通目标检测(续)

目录 3.3 实验结果与分析 3.3.1 实验数据集 3.3.2 算法的评价指标 3.3.3 损失函数实验结果...

爬虫怎么伪装才更安全

随着网络技术的不断发展&#xff0c;爬虫技术也越来越成熟&#xff0c;爬虫伪装技术也随之得到了广泛应用。在爬虫伪装技术中&#xff0c;如何伪装成正常的浏览器行为&#xff0c;让目标网站无法辨别出爬虫的存在&#xff0c;是爬虫伪装技术的核心。下面&#xff0c;我将从以下…...

openssl+sha256开发实例(C++)

文章目录 一、 sha256介绍二、sha256原理三、openssl sha256实现 一、 sha256介绍 SHA-256&#xff08;Secure Hash Algorithm 256-bit&#xff09;是一种哈希算法&#xff0c;属于 SHA-2&#xff08;Secure Hash Algorithm 2&#xff09;家族的一员。SHA-256 产生的哈希值是一…...

【Bug】当用opencv库的imread()函数读取图像,用matplotlib库的plt.imshow()函数显示图像时,图像色彩出现偏差问题的解决方法

一&#xff0c;问题描述 我们在利用opencv的imread读取本地图像&#xff0c;进行一系列处理&#xff0c;但是发现用matplotlib库的imshow&#xff08;&#xff09;函数显示的时候出现色彩改变&#xff0c;比如图像偏黄&#xff0c;偏红&#xff0c;偏蓝等等&#xff0c;但是对…...

通过顶顶通呼叫中心中间件玩转FreeSWITCH媒体流

怎么获取FreeSWITCH的媒体流是一个老生常谈的问题了&#xff0c;最常见的方法media_bug,我在2019年就做的FreeSWITCH对接ASR开源的例子https://gitcode.net/iyaosan/FreeSWITCH-ASR用的就是media_bug&#xff0c;对接ASR常见的方法还有通过mod_mrcp模块对接mrcp的asrserver。 …...

Maven内网开发使用离线仓库

Maven内网开发使用离线仓库 离线或者内网环境开发与外网不通&#xff0c;中央仓库连不上&#xff0c;使用 Maven 管理项目会遇到很多问题。 比如&#xff1a;依赖包缺失&#xff0c;内网的Nexus私服的包老旧&#xff0c;很久没有维护&#xff0c;项目无法运行打包&#xff0c;…...

CSS特效007:绘制3D文字,类似PS效果

css实战中&#xff0c;怎么绘制3D文字呢&#xff1f; 实际上理论很简单&#xff0c;使用text-shadow&#xff0c;根据需要调整阴影的颜色、大小、偏移量等参数&#xff0c;以达到你想要的立体效果。下面是一个简单的示例。关键点就是知道如何设置text-shadow。 效果图 源代码 …...

LLM 面试总结

溜一遍 MLStack.Cafe - Kill Your Next Machine Learning & Data Science Interview https://www.llmforce.com/llm-interview-questions MLStack.Cafe - Kill Your Next Machine Learning & Data Science Interview An interview with a language model, ChatGPT - W…...

acwing算法基础之数学知识--求小于等于n的所有质数

目录 1 基础知识2 模板3 工程化 1 基础知识 核心思想&#xff1a;把2~n中的非质数打上标记&#xff08;也即&#xff0c;筛掉&#xff09;&#xff0c;剩余的就是质数。 一般做法&#xff1a; int primes[N]; //存储所有的质数 int st[N]; //存储是否被排除 int cnt; int n;…...

安装和使用 nn-Meter

安装和使用 nn-Meter nn-Meter: Towards Accurate Latency Prediction of Deep-Learning Model Inference on Diverse Edge Devices nn-Meter&#xff1a;精准预测深度学习模型在边缘设备上的推理延迟 Li Lyna Zhang, Shihao Han, Jianyu Wei, Ningxin Zheng, Ting Cao, Yuqin…...

PHP原生类总结利用

再SPL介绍 SPL就是Standard PHP Library的缩写。据手册显示&#xff0c;SPL是用于解决典型问题(standard problems)的一组接口与类的集合。打开手册&#xff0c;正如上面的定义一样&#xff0c;有许多封装好的类。因为是要解决典型问题&#xff0c;免不了有一些处理文…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

Vue3中的computer和watch

computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...