UVA 1442 Cave 洞穴 （贪心+扫描）

题意：有一个洞穴，每个位置有一个底的高度p[i]，和对应顶的高度s[i]，要往里面尽量放燃料，要求燃料不能碰到顶，可以无限接近。

题解：制约燃料储放的就是顶的高度了，分别求出设当前储放位置的向两边的延伸不会碰到顶的最大高度。

设当前最大高度为level，起始位置为顶高，移动到下一格的时如果碰到顶，那么降低到s[i]，如果小于p[i]，那么就就提高到p[i]。

两边都扫一遍，然后取最小高度。

试了试输入优化，对于这种大量数据输入效果不错，节省了大约100ms。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+;

int p[maxn],s[maxn];

int h[maxn];

template<class T>

inline void scan_d(T *ret)

{

    char c;*ret=;

    while((c=getchar())<''||c>'');

    while(c>=''&&c<='') { *ret = *ret*+(c-''); c = getchar();}

}

int main()

{

    //freopen("in.txt","r",stdin);

    int T; scan_d(&T);

    while(T--){

        int n; scan_d(&n);

        for(int i = ; i < n; i++) scan_d(p+i);//scanf("%d",p+i);

        for(int i = ; i < n; i++) scan_d(s+i);//scanf("%d",s+i);

        int level = s[];

        for(int i = ; i < n; i++){

            if(level<p[i]) level = p[i];

            else if(level>s[i]) level = s[i];

            h[i] = level;

        }

        level = s[n-];

        int ans = ;

        for(int i = n-; i >=; i--){

            if(level<p[i]) level = p[i];

            else if(level>s[i]) level = s[i];

            ans += min(h[i],level) - p[i];

        }

        printf("%d\n",ans);

       // if(T) putchar('\n');

    }

    return ;

}