题目描述
mdd现在在一个异世界，这个异世界仅仅只有两个维度，可以把这个世界看成一个处在一条直线上的世界。这个世界上有很多长方形的巨石，一天，这个世界下雨了，mdd想知道这些巨石之间能存多少水呢。
输入
多组输入数据
第一行一个数n，0 <= n <= 1000。
接下来n个数，代表这些巨石的高度h，h >= 0，巨石的宽度都为1。
输出
对于每组数据，输出一行，蓄水的最大值。
输入样例
3
1 0 1
4
3 1 2 3输出样例
1
3Hint
第一组样例代表的是一组成凹字形的巨石阵|_|，中间凹下去的既是可以蓄水的部分。
算法分析
这道题的基本思想就是某个柱子A是和他后面的比它高或者和他一样高的柱子一起盛水的，而盛水量就是他们中间那些柱子和柱子A之间高度差之和。但是还要额外考虑一种情况，就是某柱子B后面没有比它还高的柱子，那么它会和他后面所有柱子中最高的柱子一起盛水。其次，不需要遍历每根柱子，比如这次算出的结果是C柱子和D柱子一起盛水，那么接下来从D柱子开始遍历就可以了，这样可以节省时间。最后输出累积的总和就可以了。
易错点
容易忘记考虑“某柱子后面没有比它还高的柱子”的盛水情况，这样算出的值会缺少一些水量。
参考代码
1 #include <cstdio>
2 using namespace std;
3
4 int stone[1005];
5
6 int main() {
7 int n;
8 while(~scanf("%d",&n)) {
9 for(int i=0;i<n;i++) {
10 scanf("%d",&stone[i]);
11 }
12 int res=0;
13 int flag=0;
14 for(int i=0;i<n-2;i++) {
15 if(stone[i]>stone[i+1]) {
16 flag=0;
17 for(int j=i+1;j<n;j++) {
18 if(stone[j]>=stone[i]) {
19 flag=1;
20 for(int k=i+1;k<j;k++) {
21 res+=(stone[i]-stone[k]);
22 }
23 i=j-1;
24 break;
25 }
26 }
27 if(!flag) {
28 int maxi=0;
29 int maxIndex=0;
30 for(int j=i+1;j<n;j++) {
31 if(stone[j]>maxi) {
32 maxi=stone[j];
33 maxIndex=j;
34 }
35 }
36 for(int j=i+1;j<maxIndex;j++) {
37 res+=(maxi-stone[j]);
38 }
39 if(maxIndex==n-1) break;
40 else i=maxIndex-1;
41 }
42 }
43 }
44 printf("%d\n",res);
45 }
46 }
47
48 /*
49 7
50 3 1 2 3 1 0 1
51 */