二维立柱图|积水类问题

三类问题
- 求总的积水量
- 求水坑的个数
- 求水坑最深的深度
基本思路
我们需要从列的角度来看第 i i i 列是不是有积水,但我们该如何确定第 i i i 列是否是有积水?
方法是事先维护一个前后缀的最大值, L [ i ] L[i] L[i] 和 R [ i ] R[i] R[i] 分别表示 [ 1 , i ] [1,i] [1,i] 和 [ i , n ] [i,n] [i,n] 中障碍物的最高高度,那么对于第 i i i 列,如果满足 L [ i ] > h [ i ] & & h [ i ] < R [ i ] L[i]> h[i] ~\&\&~ h[i]< R[i] L[i]>h[i] && h[i]<R[i],那么就证明它是低洼地,且水深就是 m i n ( L [ i ] , R [ i ] ) − h [ i ] min(L[i],R[i])-h[i] min(L[i],R[i])−h[i]。
准备工作
int h[N], L[N], R[N], n;
//分别记录第i列的障碍物高度以及前后缀最大值
void work() {cin >> n;for (int i = 1; i <= n; i++) cin >> h[i];for (int i = 1; i <= n; i++) L[i] = max(L[i - 1], h[i]);for (int i = n; i >= 1; i--) R[i] = max(R[i + 1], h[i]);
}
求总的积水量
int get_sum() {int sum = 0;for (int i = 1; i <= n; i++) {if (L[i] > h[i] && h[i] < R[i]) {sum += min(L[i], R[i]) - h[i];}}return sum;
}
求水坑的个数
注意:即使两个相邻的水坑有相同高度的水平面,只要之间有障碍物相隔,就算是两个水坑。
解决办法:引入一个标记状态的数组 s t [ N ] st[N] st[N],表示第 i i i 列是否是水坑的一条,如果 s t [ i ] = = t r u e & & s t [ i − 1 ] = = t r u e st[i]==true~\&\&~st[i-1]==true st[i]==true && st[i−1]==true,那么就说明了他们是属于同一水坑,否则第 i i i 列就属于一个新的水坑。
bool st[N];//表示第i列是否是水坑的一条
int get_cnt() {int cnt = 0;for (int i = 1; i <= n; i++) {if (L[i] > h[i] && h[i] < R[i]) {if (!st[i - 1]) cnt++;st[i] = true;}}return cnt;
}
求水坑的最深的深度
int get_mx() {int mx = 0;for (int i = 1; i <= n; i++) {if (L[i] > h[i] && h[i] < R[i]) {mx = max(mx, min(L[i], R[i]) - h[i]);}}return mx;
}
例题
- 积水量 http://bailian.openjudge.cn/practice/4074/
- 有多少坑
题目描述
大雨过后,一些高低不平的地方就会形成积水,俗称为“坑”。
这里我们将问题简化为只考虑一段路面的横截面。我们将这一段截面上的土地分割成单位宽度的窄条,测量出每个窄条的高度。
假设有无穷多的水量从天而降,请你计算一下,这段路面上会形成多少个水坑?坑的最大深度是多少毫米?
输入
输入第一行给出一个正整数 N ( ≤ 100000 ) N(\leq 100000) N(≤100000)。随后一行给出 N N N 个非负整数,为路面横截面总左到右的单位宽度窄条的高度,以毫米为单位,不超过 1000 1000 1000。
输出
输出分两行,第一行输出水坑的个数,第二行输出所有水坑中最大的深度,以毫米为单位。
注意:即使两个相邻的水坑有相同高度的水平面,只要之间有窄条相隔,就算是两个水坑。
样例输入
12
1 4 2 10 7 1 2 1 8 3 1 2
样例输出
3
7
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int h[N], L[N], R[N], n;
//分别记录第i列的障碍物高度以及前后缀最大值
bool st[N];//表示第i列是否是水坑的一条
void work() {cin >> n;for (int i = 1; i <= n; i++) cin >> h[i];R[n + 1] = 0;for (int i = 1; i <= n; i++) L[i] = max(L[i - 1], h[i]);for (int i = n; i >= 1; i--) R[i] = max(R[i + 1], h[i]);
}
int get_cnt() {int cnt = 0;for (int i = 1; i <= n; i++) {if (L[i] > h[i] && h[i] < R[i]) {if (!st[i - 1]) cnt++;st[i] = true;}}return cnt;
}
int get_mx() {int mx = 0;for (int i = 1; i <= n; i++) {if (L[i] > h[i] && h[i] < R[i]) {mx = max(mx, min(L[i], R[i]) - h[i]);}}return mx;
}
int main() {work();cout << get_cnt() << "\n" << get_mx();return 0;
}
相关文章:

二维立柱图|积水类问题
三类问题 求总的积水量求水坑的个数求水坑最深的深度 基本思路 我们需要从列的角度来看第 i i i 列是不是有积水,但我们该如何确定第 i i i 列是否是有积水? 方法是事先维护一个前后缀的最大值, L [ i ] L[i] L[i] 和 R [ i ] R[i] R[…...

vue前端实现导出页面为word(两种方法)
将vue页面导出为word文档,不用写模板,直接导出即可。 第一种方法(简单版) 第一步:安装所需依赖 npm install html-docx-js -S npm install file-saver -S第二步:创建容器,页面使用方法(简单版࿱…...

22. Three.js案例-创建旋转的圆环面
22. Three.js案例-创建旋转的圆环面 实现效果 知识点 WebGLRenderer (WebGL渲染器) THREE.WebGLRenderer 是Three.js中最常用的渲染器,用于将场景渲染到WebGL画布上。 构造器 new THREE.WebGLRenderer(parameters) 参数类型描述parametersObject可选参数对象&…...

Elasticsearch:使用阿里 infererence API 及 semantic text 进行向量搜索
在之前的文章 “Elasticsearch 开放推理 API 新增阿里云 AI 搜索支持”,它详细描述了如何使用 Elastic inference API 来针对阿里的密集向量模型,稀疏向量模型, 重新排名及 completion 进行展示。在那篇文章里,它使用了很多的英文…...

Linux WEB服务器的部署及优化
1.用户常用关于web的信息 1.1.什么是www www是world wide web的缩写,及万维网,也就是全球信息广播的意思。 通常说的上网就是使用www来查询用户所需要的信息。 www可以结合文字、图形、影像以及声音等多媒体,超链接的方式将信息以Internet…...

人工智能大模型LLM开源资源汇总(持续更新)
说明 目前是大范围整理阶段,所以存在大量机翻说明,后续会逐渐补充和完善资料,减少机翻并增加说明。 Github上的汇总资源(大部分英文) awesome-production-machine-learning 此存储库包含一系列精选的优秀开源库&am…...

目标跟踪算法:SORT、卡尔曼滤波、匈牙利算法
目录 1 目标检测 2 卡尔曼滤波 3《从放弃到精通!卡尔曼滤波从理论到实践》视频简单学习笔记 3.1 入门 3.2 进阶 3.2.1 状态空间表达式 3.2.2 高斯分布 3.3 放弃 3.4 精通 4 匈牙利算法 5 《【运筹学】-指派问题(匈牙利算法)》视…...

Java版-图论-拓扑排序与有向无环图
拓扑排序 拓扑排序说明 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列…...

GTC2024 回顾 | 优阅达携手 HubSpot 亮相上海,赋能企业数字营销与全球业务增长
从初创企业入门到成长型企业拓展,再到 AI 驱动智能化运营,HubSpot 为企业的每步成长提供了全方位支持。 2024 年 11 月下旬,备受瞩目的 GTC2024 全球流量大会(上海)成功举办。本次大会汇聚了全国内多家跨境出海领域企业…...

eclipse启动的时候,之前一切很正常,但突然报Reason: Failed to determine a suitable driver class的解决
1、之前项目都是启动正常的,然后运行以后发现启动不了了,还会报错: 2、这个Reason: Failed to determine a suitable driver class,说是没有合适的驱动class spring:datasource:url: jdbc:sqlserver://192.168.1.101:1433;databa…...
_tkinter.TclError: can‘t find package tkdnd Unable to load tkdnd library.解决办法
Traceback (most recent call last): File “tkinterdnd2\TkinterDnD.py”, line 55, in _require _tkinter.TclError: can’t find package tkdnd During handling of the above exception, another exception occurred: Traceback (most recent call last): File “1.导入总表…...

VBA高级应用30例应用在Excel中的ListObject对象:向表中添加注释
《VBA高级应用30例》(版权10178985),是我推出的第十套教程,教程是专门针对高级学员在学习VBA过程中提高路途上的案例展开,这套教程案例与理论结合,紧贴“实战”,并做“战术总结”,以…...
folly库Conv类型转换源码解析
1,普通类型转换 例子1: bool boolV = true;EXPECT_EQ(to<bool>(boolV), true);int intV = 42;EXPECT_EQ(to<int>(intV), 42);float floatV = 4.2f;EXPECT_EQ(to<float>(floatV), 4.2f);double doubleV = 0.42;EXPECT_EQ(to<double>(doubleV), 0.42)…...
UE4 骨骼网格体合并及规范
实现代码 // Fill out your copyright notice in the Description page of Project Settings.#pragma once#include "CoreMinimal.h" #include "SkeletalMeshMerge.h" #include "Kismet/BlueprintFunctionLibrary.h" #include "AceMeshCom…...

Java版企业电子招标采购系统源业码Spring Cloud + Spring Boot +二次开发+ MybatisPlus + Redis
功能描述 1、门户管理:所有用户可在门户页面查看所有的公告信息及相关的通知信息。主要板块包含:招标公告、非招标公告、系统通知、政策法规。 2、立项管理:企业用户可对需要采购的项目进行立项申请,并提交审批,查看所…...
通过源码⼀步⼀步分析 ArrayList 扩容机制
ArrayList 是 Java 中常用的集合类,它底层实现是基于数组的。为了处理元素的动态增加,ArrayList 会在容量不足时进行扩容。以下是通过源码逐步分析 ArrayList 扩容机制的过程。 1. ArrayList 类的基本结构 ArrayList 继承自 AbstractList,实…...
源码分析之Openlayers中默认Controls控件渲染原理
概述 Openlayers 中默认的三类控件是Zoom、Rotate和Attribution 源码分析 defaults方法 Openlayers 默认控件的集成封装在defaults方法中,该方法会返回一个Collection的实例,Collection是一个基于数组封装了一些方法,主要涉及到数组项的添…...
中间件的分类与实践:从消息到缓存
目录 一. 中间件的基本概念 二. 中间件的主要类型 (1)消息中间件(Message-Oriented Middleware, MOM): (2)数据库中间件: (3)Web中间件: &a…...

京东e卡 h5st 4.96
声明: 本文章中所有内容仅供学习交流使用,不用于其他任何目的,抓包内容、敏感网址、数据接口等均已做脱敏处理,严禁用于商业用途和非法用途,否则由此产生的一切后果均与作者无关! 有相关问题请第一时间头像私信联系我删…...
《CSS 知识点》滚动条仅在 hover 时才显示(宽度不改变)
很简单! 滚动条的滑动小方块背景色默认透明,仅在hover时设置背景色; 滚动条的轨道背景色默认透明,仅在hover时设置背景色; /*滚动条的滑动小方块*/ ::-webkit-scrollbar-thumb {background: transparent; } /*hover…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...

前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...

SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

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

R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

【 java 虚拟机知识 第一篇 】
目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分: 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...