洛谷 P1318 积水面积-白红宇

题目描述

一组正整数，分别表示由正方体迭起的柱子的高度。若某高度值为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：

0 1 0 2 1 2 0 0 2 0

输出样例#1：

解题思路

找出最高的一根柱子，从最高的一行起，一行一行向下扫描，每行扫描一遍找出最左边的一根和最右边的一根，他们之间每一个没有柱子的地方贡献一个面积的积水（好像没毛病），然后把每行答案加起来，就得到总的可能积水面积了

维护前缀最大值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
      
       #include
       
        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