二维立柱图|积水类问题

三类问题

• 求总的积水量
• 求水坑的个数
• 求水坑最深的深度

基本思路

我们需要从列的角度来看第 $i$ 列是不是有积水，但我们该如何确定第 $i$ 列是否是有积水？

方法是事先维护一个前后缀的最大值，$L[i]$ 和 $R[i]$ 分别表示 $[1,i]$ 和 $[i,n]$ 中障碍物的最高高度，那么对于第 $i$ 列，如果满足 $L[i]>h[i]\&\&h[i]<R[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;
}

求水坑的个数

注意：即使两个相邻的水坑有相同高度的水平面，只要之间有障碍物相隔，就算是两个水坑。

解决办法：引入一个标记状态的数组 $st[N]$，表示第 $i$ 列是否是水坑的一条，如果 $st[i]==true\&\&st[i-1]==true$，那么就说明了他们是属于同一水坑，否则第 $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(\le 100000)$。随后一行给出 $N$ 个非负整数，为路面横截面总左到右的单位宽度窄条的高度，以毫米为单位，不超过 $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;
}