题目描述
一组正整数，分别表示由正方体迭起的柱子的高度。若某高度值为x，表示由x个正立方的方块迭起（如下图，0<=x<=5000）。找出所有可能积水的地方（图中蓝色部分），统计它们可能积水的面积总和（计算的是图中的横截面积。一个立方体的位置，为一个单位面积）。
如图：柱子高度变化为 0 1 0 2 1 2 0 0 2 0
图中蓝色部分为积水面积，共有6个单位面积积水。
输入输出格式
输入格式：
两行，第一行n,表示有n个数(3<=n<=10000)。第2行连续n个数表示依次由正方体迭起的高度，保证首尾为0。
输出格式：
一个数，可能积水的面积。
输入输出样例
输入样例#1：
10
0 1 0 2 1 2 0 0 2 0
输出样例#1：
6
解题思路
- 找出最高的一根柱子，从最高的一行起，一行一行向下扫描，每行扫描一遍找出最左边的一根和最右边的一根，他们之间每一个没有柱子的地方贡献一个面积的积水（好像没毛病），然后把每行答案加起来，就得到总的可能积水面积了
- 维护前缀最大值fro[i]和后缀最大值beh[i]，对每一列对面积的贡献为h[i]-min(fro[i],beh[i])，然后从左到右，对每一列都有ans+=h[i]-min(fro[i],beh[i])（这不是显然的吗）
- 维护一个单调栈，还没搞懂
- 以上思路源码https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1318
- 自己的思路：对所有h[i]，在记录了原本位置的情况下对高度进行排序，然后枚举：对第一高的和第二高的（一样高也可以）之间所有列统计答案，标记已统计过（因为后面不能重复计算这一列，降序排序保证了越靠前计算获得水位越高），对第二高和第三高之间区间执行相同操作，对第三高和第四高区间之间执行相同操作……，第n-1高和第n高（最矮）之间区间执行相同操作，最后输出答案，ac
源码（自己思路5）
#include<cstdio> #include<algorithm> using namespace std; struct data{ int high;//柱子高度 int num;//记录原图中柱子的编号，因为排序会打乱编号 }d[100100]; int n; bool vis[100100]={0};//判断是否放过水 int h[100100]={0};//按顺序排列的柱子高度 int ans=0; int cmp(const data & a,const data & b) { return a.high>b.high;//cmp函数等于的情况要么特判，要么不管，不然re（a.high>=b.high)，我不知道为什么，有知道的大牛能否告知？ } int main() { scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",h+i); d[i].high=h[i]; d[i].num=i; } sort(d,d+n,cmp); for(int i=0;i<n-1;i++) { int left = min(d[i].num,d[i+1].num); int right= max(d[i].num,d[i+1].num);//找到待修改区间的左右端点，端点处不用算，贡献面积为0 int hh=min(h[right],h[left]);//液面高度为两端点中更低的柱子的高度 vis[right]=vis[left]=true; for(left+=1;left<right;left++) { if(!vis[left]) { vis[left]=true; ans+=hh-h[left];//一根柱子积水高度为液面高度减去柱子高度,因为是按从高到低的顺序操作的,所以可以保证减得的结果不为负 } } } printf("%d",ans); return 0; }
![洛谷P3194 [HNOI2008]水平可见直线（计算几何+单调栈）](https://ucc.alicdn.com/pic/developer-ecology/288141e3914546aa9a639ec3958e111b.png?x-oss-process=image/resize,h_160,m_lfit)