链接：
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4188
题意：
一个洞穴的宽度由n（n≤1e6）个片段组成。已知位置[i,i+1]处的地面高度pi和顶的高度si（0≤pi＜si≤1000），
要求在这个洞穴里储存尽量多的燃料，使得在任何位置燃料都不会碰到顶（但是可以无限接近）。
分析：
扫描法。
为了方便起见，下面用“水”来代替题目中的燃料。根据物理定律，每一段有水的连续区间，
水位高度必须相等，且水位必须小于等于区间内的最低天花板高度，因此位置[i,i＋1]处的水位满足h≤si，
且从(i,h)出发往左右延伸出的两条射线均不会碰到天花板（即两条射线将一直延伸到
洞穴之外或先碰到地板之间的“墙壁”）。如果这样的h不存在，则规定h=pi（也就是“没水”）。
这样，可以先求出“往左延伸不会碰到天花板”的最大值h1(i)，再求“往右延伸不会碰到
天花板”的最大值h2(i)，则hi=min{h1(i), h2(i)}。根据对称性，下面只考虑h1(i)的计算：
从左到右扫描。初始时设水位level=s0，然后依次判断各个位置[i,i＋1]处的高度。
如果p[i] ＞ level，说明水被“隔断”了，需要把level提升到pi。
如果s[i] ＜ level，说明水位太高，碰到了天花板，需要把level下降到si。
位置[i,i＋1]处的水位就是扫描到位置i时的level。
不难发现，两次扫描的时间复杂度均为O(n)，总时间复杂度为O(n)。
代码：
#include <cstdio>
#include <algorithm>
using namespace std; const int UP = 1e6 + ;
int p[UP], s[UP], h[UP]; int main(){
int T;
scanf("%d", &T);
while(T--){
int n;
scanf("%d", &n);
for(int i = ; i < n; i++) scanf("%d", &p[i]);
for(int i = ; i < n; i++) scanf("%d", &s[i]); int ans = , level = s[];
for(int i = ; i < n; i++){
if(p[i] > level) level = p[i];
else if(s[i] < level) level = s[i];
h[i] = level;
} level = s[n-];
for(int i = n - ; i >= ; i--){
if(p[i] > level) level = p[i];
else if(s[i] < level) level = s[i];
ans += min(level, h[i]) - p[i];
}
printf("%d\n", ans);
}
return ;
}