[紫书][思维] 非常见模型 物理 思维与分析 UVa1442

紫书第八章这些题。。有点意思的啊。。

题意让往一个不规则的二维洞穴里面加水问每个地方都不碰到天花板的话最多能装多少水。当然很容易想到用在一点画一条横线然后与其他天花板不相交，但是没想出来怎么在低复杂度求和具体实现。看了紫书题解，才发现这条横线左右两边可以分开来求，这样求一边的时候就可以扫描一遍数组而不用O(n^2)去计算了，

因为只考虑一边的话可以利用之前求过的上限水位level的信息，比如要求hleft，那么从左向右扫描就可以了，因为这时候不用管右边的所以只用关心左边传过来的level是否淹到了当前点的天花板（这时候需要降低上限水位变成天花板的高度）或者是没有淹过地板（这时候要提高上限水位，因为这相当于水在中间被阻断了，之后的水位只要不超过这个阻断的“水坝”就可以了）

#include 
#include

using namespace std;

typedef long long LL;
const int maxn=1e6+5;
const int MOD=1e9+7;

int s[maxn],p[maxn],hl[maxn],hr[maxn];

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    int z,n,ans;
    scanf("%d",&z);
    while(z--)
    {
        ans=0;
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
            scanf("%d",&p[i]);
        for (int i=1;i<=n;i++)
            scanf("%d",&s[i]);
        hl[1]=s[1];
        hr[n]=s[n];
        for (int i=2,level=hl[1];i<=n;i++)
        {
            if(level>s[i])
            {
                level=s[i];
            }
            if(level=1;i--)
        {
            if(level>s[i])
            {
                level=s[i];
            }
            if(level