洛谷 P1318 积水面积

洛谷 P1318 积水面积

链接

https://www.luogu.org/problem/P1318

题目

题目描述

一组正整数,分别表示由正方体叠起的柱子的高度。若某高度值为x,表示由x个正立方的方块迭起(如下图,0<=x<=5000)。找出所有可能积水的地方(图中蓝色部分),统计它们可能积水的面积总和(计算的是图中的横截面积。一个立方体的位置,为一个单位面积)。

如图:柱子高度变化为 0 1 0 2 1 2 0 0 2 0

img

图中蓝色部分为积水面积,共有6个单位面积积水。

输入格式

两行,第一行n,表示有n个数(3<=n<=10000)。第2行连续n个数表示依次由正方体迭起的高度,保证首尾为0。

输出格式

一个数,可能积水的面积。

输入输出样例

输入 #1

1
2
10
0 1 0 2 1 2 0 0 2 0

输出 #1

1
6

思路

我的思路是左右向中间,从下往上。

首先输入,找到最大值,之后从1开始循环,这个j是高度的意思,left和right就是左右达到这个高度的最前一个,之后添加数字,直接判断大小就行,到最后一个结束,输出结果。

(最近心态不好,人很迷茫,估计骚话环节也没了,以上)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
int maxn,ans;
int num[12580];
int n,left,right;
cin>>n;

for(int i=1;i<=n;i++)
{
cin>>num[i];
maxn=max(maxn,num[i]);
}

for(int j=1;j<=maxn;j++)
{
for(int i=2;i<=n-1;i++)
{
if(num[i]>=j)
{
left=i;
i=n;
}
}
for(int i=n-1;i>=2;i--)
{
if(num[i]>=j)
{
right=i;
i=1;
}
}

for(int i=left;i<right;i++)
{
if(num[i]<j)
ans++;
}

}
cout<<ans;
}
---本文结束,感谢阅读---