4074:积水量
总时间限制: 1000ms 内存限制: 65536kB
描述
凹凸不平的地面每当下雨的时候总会积水。假设地面是一维的，每一块宽度都为1，高度是非负整数，那么可以用一个数组来表达一块地面。例如[0,1,0,2,1,0,1,3,2,1,2,1]可以用来表示下图地面：
当下过雨后，地面就会积水，上图中蓝色的区域就是积水区域。现在给你一个数组表示地面，求下过雨后这块地面有多少积水量（假设不蒸发、不渗透）。
输入
第一行是一个整数m，表示有m组试样例，不超过100。
接下来m块，每块第一行是一个正整数n，表示地面总宽度（数组长度），不超过20000。
接下来一行是n个整数，用空格隔开，表示地面高度。
输出
对于每组输入，输出一个整数表示积水量。
样例输入
2
12
0 1 0 2 1 0 1 3 2 1 2 1
4
1 0 0 2
样例输出
6
2
问题链接：Bailian4074 积水量
问题简述：（略）
问题分析：先算最大高度，积水有可能在2个最大高度之间的地方。然后一层一层计算积水，从1到最大高度逐层计算，先计算第1层的积水，…。计算第i层积水时，先找出2边柱子（从左到右找大于或等于i的柱子，从右到左找大于或等于i的柱子），第i层积水则在这两个柱子之间，中间低于i的柱子这一层都有积水。
程序说明：（略）
参考链接：（略）
题记：（略）
AC的C++语言程序如下：
/* Bailian4074 积水量 */
#include <bits/stdc++.h>
using namespace std;
const int N = 20000;
int height[N + 2];
int calculate(int left, int right, int h)
{
int sum = 0;
for(int i = left + 1; i < right; i++)
if(height[i] < h) sum++;
return sum;
}
int main()
{
int m, n;
scanf("%d", &m);
while(m--) {
scanf("%d", &n);
int maxh = 0;
for(int i = 0; i < n; i++) {
scanf("%d", &height[i]);
maxh = max(maxh, height[i]);
}
int sum = 0;
for(int i = 1; i <= maxh; i++) {
int left = 0, right = 0;
for(int j = 0; j < n; j++)
if(height[j] >= i) {
left = j;
break;
}
for(int j = n - 1; j >= 0; j--)
if(height[j] >= i) {
right = j;
break;
}
sum += calculate(left, right, i);
}
printf("%d\n", sum);
}
return 0;
}