二维立柱图|积水类问题

三类问题
- 求总的积水量
- 求水坑的个数
- 求水坑最深的深度
基本思路
我们需要从列的角度来看第 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…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...

Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...

SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...