2016广东工业大学校赛 E题 GDUT-oj1173

时间：2024-10-08 18:37:14

Problem E: 积木积水

Description

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

2016广东工业大学校赛 E题 GDUT-oj1173

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

19
题意：搭好积木 能装多少水？ 题目很好理解
题解：刚开始思路错误 想着不断寻找最高积木与次高积木 然后判断之间能存多少水 TLE
        AC 代码 考虑每一列积木能贡献多少积水 记录当前列的左max与右max
       然后遍历答案ans+=min(l[i],r[i])-a[i];
 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<stack>

 #include<map>

 #include<set>

 #define ll long long

 #define Pi acos(-1.0)

 #define mod 1

 #define MAX 100000

 #define bug(x) printf("%d************\n",x);

 using namespace std;

 #define ll long long

 int a[];

 int r[];

 int l[];

 int main()

 {

     int x,y,z,i,t;

     scanf("%d",&x);

     while(x--)

     {

         memset(l,,sizeof(l));

         memset(r,,sizeof(r));

         scanf("%d",&y);

         for(i=;i<y;i++)

         scanf("%d",&a[i]);

         int maxx=;

         for(i=;i<y;i++)

         {

             maxx=max(maxx,a[i-]);

             l[i]=maxx;

         }

         maxx=;

         for(i=y-;i>=;i--)

         {

             maxx=max(maxx,a[i+]);

             r[i]=maxx;

         }

         ll ans=;

         for(i=;i<y;i++)

         {

             if(min(l[i],r[i])>a[i])

             ans+=min(l[i],r[i])-a[i];

         }

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

     }

     return ;

 }

 /**************************************************************

     Problem: 1173

     User: 853665920

     Language: C++

     Result: Accepted

     Time:624 ms

     Memory:13496 kb

 ****************************************************************/

相关文章