一、题意

一个山洞的宽度由n个片段构成，每个片段有个地面高度floor[maxn]和天花板高度ceil[maxn]。
现在往里面装水，要求各个地方的水位不能淹没天花板，求最多能装多少水。（山洞两侧为无限高的墙壁）

二、解析

这是一道超经典的水位问题。以前在leetcode上做过一道简化版：
即没有天花板之说，只给出各个地方的地面高度floor[maxn]，输出最多能装多少水。

我们先来讨论这个弱化版：我们都知道一块地方的最高水位取决于它左侧的最大高度和右侧最大高度这二者的最小值，因此我们首先维护出两个数组l_top[i]和r_top[i]分别表示位置i的左侧和右侧的最大高度。也就是l_top[i] = max(l_top[i-1], floor[i])，r_top[i]同理。这时这个位置i能装的最大水量就是min(l_top[i], r_top[i])-floor[i]，当然前提是位置i的地面高度低于两侧最大高度的最小值。这样这道题目就只需要遍历一次求出l_top[maxn]，在再遍历一次求出r_top[maxn]，然后最后遍历一次将各个地方的最大水量计算出来并累计起来即可。

回到本题，这道题多加了一个天花板ceil[maxn]的限制。实际上是一样的，l_top[maxn]在弱化版中表示的是左侧的位置中海拔的最大值，而由于出现了天花板的限制，因此这个最大值是达不到的。也就是说我们在计算l_top[maxn]时要同时考虑天花板的限制，也就是l_top[i] = min(l_top[i], ceil[i])。

因此，结合起来，本题的l_top[i] = min(max(l_top[i - 1], floor[i - 1]), ceil[i])。r_top[i]同理。这样就能和弱化版的水位题一样，用O(n)时间得到答案了。

三、代码

#include <iostream>
using namespace std;
const int maxn = 1000000 + 5, INF = 1 << 30;
int kase, n, floor[maxn], ceil[maxn], l_top[maxn], r_top[maxn];

int main() {
    cin >> kase;
    while(kase --) {
        cin >> n;
        for(int i = 1; i <= n; i ++) cin >> floor[i];
        for(int i = 1; i <= n; i ++) cin >> ceil[i];
        l_top[0] = r_top[n + 1] = INF;
        for(int i = 1; i <= n; i ++) l_top[i] = min(max(l_top[i - 1], floor[i - 1]), ceil[i]);
        for(int i = n; i >= 1; i --) r_top[i] = min(max(r_top[i + 1], floor[i + 1]), ceil[i]);
        int ans = 0;
        for(int i = 1; i <= n; i ++) if(min(l_top[i], r_top[i]) > floor[i]) ans += min(l_top[i], r_top[i]) - floor[i];
        cout << ans << endl;
    }
}

四、归纳

  • 水位问题：通过预处理得到l_top[maxn]和r_top[maxn]数组，分别表示位置i的左侧和右侧的最大高度。也就是只需要遍历一次求出l_top[maxn]，在再遍历一次求出r_top[maxn]，然后最后遍历一次将各个地方的最大水量计算出来并累计起来即可。