鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > c++ > >

编程题:墙里能装多少水

来源:互联网 作者:佚名 时间:2013-11-29 10:40
题目: 输入可表示为一组墙的数组a,其中a[i]表示第i堵墙的高度。假如下雨了,墙里最多能装多少水? 例: 这种情况下为10,最左边和最右边的水都漏掉了。 来源: 解答: 思路(1): 将问题转为函数f(m, n),即[m, n]区间内的存水量。设i为(m, n)区间中的最

题目:

输入可表示为一组墙的数组a,,其中a[i]表示第i堵墙的高度。假如下雨了,墙里最多能装多少水?

例:

QQ截图20131117225404

这种情况下为10,最左边和最右边的水都漏掉了。

来源:

解答:

思路(1):

将问题转为函数f(m, n),即[m, n]区间内的存水量。设i为(m, n)区间中的最大值位置,则有性质:

代码如下:

int Water(int *a, int m, int n) { if (m-n < 2) return 0; int i = 1; for (int j = m+1; j < n; ++j) if (a[i] < a[j]) i = j; int volume = 0; if (a[i] <= a[m] && a[i] <= a[n]) { int height = min(a[m], a[n]); for (int j = m+1; j < n; ++j) volume += height-a[j]; } else if (a[i] <= a[m]) { int height = min(a[i], a[m]); for (int j = m+1; j < i; ++j) volume += height-a[j]; volume += Water(a, i, n); } else if (a[i] <= a[n]) { int height = min(a[i], a[n]); for (int j = i+1; j < n; ++j) volume += height-a[j]; volume += Water(a, m, i); } else { volume = Water(a, m, i) + Water(a, i, n); } return volume; }

思路(2):

若知道区间的右边界比左边界高,则存水高度就是由左边界确定的,此时将左边界向右移动,途中就可以直接计算在该墙之上的存水量是多少。若在移动过程中遇到了比左边界高的墙,说明之前移动扫过的是一个单独的水坑。这种方法只需要遍历一次数组,时间复杂度O(n)。

代码如下:

int Water(int *a, int n) { if (n < 3) return 0; int maxl = a[0], posl = 0; int maxr = a[n-1], posr = n-1; int volume = 0; while (posl < posr) { if (maxl < maxr) { ++posl; if (a[posl] > maxl) maxl = a[posl]; else volume += maxl-a[posl]; } else { --posr; if (a[posr] > maxr) maxr = a[posr]; else volume += maxr-a[posr]; } } return volume; }

网友评论
<