广东工业大学网络赛E题思维题

阳光穿透心脏的1/2处 2022-07-30 13:15 272阅读 0赞

## Problem E: 积木积水 ##

## Description ##

现有一堆边长为1的已经放置好的积木，小明（对的，你没看错，的确是陪伴我们成长的那个小明）想知道当下雨天来时会有多少积水。小明又是如此地喜欢二次元，于是他把这个三维的现实问题简化成二维的问题。设雨量无穷、积木不透水、积木间无缝连接，问在这个二次元的世界里，已放置好的积木会有多少单位的积水量？

![image_2F_E7_A7_AF_E6_9C_A8_E7_A7_AF_E6_B0_B4_E5_9B_BE.png][]

## Input ##

第一行包含一个整数T(T≤100)，表示接下来的测试样例个数。 每个测试样例有两行组成： 第一行包含一个整数N(N≤1e6)，表示积木的列数； 第二行包含N个整数Ai(Ai≤1e6)，表示第i列积木的个数。

## Output ##

每个样例输出一行，包含一个整数，为题目所求。

## Sample Input ##

1  
11  
6 2 2 4 2 0 3 4 4 5 1

## Sample Output ##

## HINT ##

题意: 求积木会积多少水.

分析: 我们可以从左到右, 对于每一个积木, 求他左右两边的最高的积木中小的一个, 就是这个积木会积水的量. 遍历每一个统计总值就行了.

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    #define F first
    #define S second
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;int f=1;
        while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res*f;
    }
    const int N=1000010,MOD=1e9+7;
    int a[N],l[N],r[N];
    
    int main()
    {
        int T=in();
        while(T--)
        {
            int n=in();
            for(int i=1;i<=n;i++)
            {
                a[i]=in();
            }
            l[0]=0;
            for(int i=1;i<=n;i++)
            {
                l[i]=max(l[i-1],a[i]);
            }
            r[n+1]=0;
            for(int i=n;i;i--)
            {
                r[i]=max(r[i+1],a[i]);
            }
            ll tot=0;
            for(int i=2;i<n;i++)
            {
                tot += max(min(l[i-1],r[i+1])-a[i],0);
            }
            printf("%lld\n",tot);
        }
        return 0;
    }

[image_2F_E7_A7_AF_E6_9C_A8_E7_A7_AF_E6_B0_B4_E5_9B_BE.png]: http://gdutcode-gdutcode.stor.sinaapp.com/image%2F%E7%A7%AF%E6%9C%A8%E7%A7%AF%E6%B0%B4%E5%9B%BE.png