题目描述
一组正整数，分别表示由正方体迭起的柱子的高度。若某高度值为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
思路：一层一层的从底下找。因为题目中说：“正立方的方块迭起。”，所以就不会出现一些特殊情况。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int maxn,ans; int num[10010]; int n,l,r,find; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&num[i]); maxn=max(maxn,num[i]); } for(int k=1;k<=maxn;k++){ for(int i=2;i<=n-1;i++) if(num[i]>=k){ l=i;break; } for(int i=n-1;i>=2;i--) if(num[i]>=k){ r=i;break; } for(int i=l;i<r;i++) if(num[i]<k) ans++; } cout<<ans<<endl; }