手机网站竞价,没有网站可以域名备案,手机网站的内容模块,旅游网站排名相关推荐三类问题
求总的积水量求水坑的个数求水坑最深的深度
基本思路
我们需要从列的角度来看第 i i i 列是不是有积水#xff0c;但我们该如何确定第 i i i 列是否是有积水#xff1f;
方法是事先维护一个前后缀的最大值#xff0c; L [ i ] L[i] L[i] 和 R [ i ] R[i] R[…
三类问题
求总的积水量求水坑的个数求水坑最深的深度
基本思路
我们需要从列的角度来看第 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;
}
