题意简述

给出n个柱子的高度,柱子之间的空隙可以积水,求出最大的积水面积总和。


一道很有意思的模拟题,一开始还没有什么思路,后来发现没有柱子可以悬空,模拟的思路就大概出来了。

我的思路很简单比较好想,就是把柱子分层。

例如题目中的样例,最高的柱子高2个单位长度,那么就把它分为2层,for循环遍历每一层,我们可以发现只要是两侧有柱子的空隙就能接水,就像这个图:

第一层可以找到3个满足这种性质的空隙,第二层也是三个。

$ $

那如果是这样的柱子呢:

虽然最高有2层,即分为2层,但是第二层找不出两个柱子之间的空隙,这种情况可以直接break掉,因为这样的情况一定是在最高层才可能出现。


所以这题就很简单了,读入时进行处理找到最高层,然后进行分层,很明显层数为最高层数。然后写一个getsum函数寻找最左端与最右端的下标,如果一样则没有可以接水的空隙,反之看看这段区间内有多少地方是空的


我是可爱的代码菌OvO:

# include <cstdio>
# include <cstdlib>
# include <iostream>
# include <algorithm>
using namespace std;

inline void gi(int &x)    //get_int 快读
{
    x=0;int t=1,k=getchar();
    for(;k<'0'||k>'9';k=getchar())if(k=='-')t=-1;
    for(;k>='0'&&k<='9';k=getchar())x=(x<<1)+(x<<3)+(k^48);x*=t;
}

const int N=10003;
int n, a[N], maxh, h;
int l, r;
bool lf=false, rf=false;
long long ans;

void debug()    //debug函数,可以忽略
{
      for(int i=1; i<=n; ++i)
        cout << a[i] << " ";
      puts("");
      cout << l << " " << r << endl;
      system("pause");
}

inline void getsum()    //简陋的寻找下标函数
{
      lf=rf=false;    //判断是否有柱子出现
      for(register int i=1; i<=n; ++i)
        if(a[i])
        {
          lf=true;
          l=i;    //最左端柱子的下标
          break;
        }

      for(register int i=n; i>=1; --i)
        if(a[i])
        {
          rf=true;
          r=i;    //最右端柱子的下标
          break;
        }
      return ;
}

int main(void)
{
      gi(n);
      for(int i=1; i<=n; ++i)
      {
        gi(a[i]);
        maxh=maxh < a[i] ? a[i] : maxh;    //找到最大高度,即层数
      }
      if(!maxh) goto Re;    //小优化,最高层为0一定没有可积水的面积
      for(int i=1; i<=maxh; ++i)    //按层数依次推进
      {
        getsum();
        if(!lf || !rf) break;    //没有找到柱子可以直接break
        for(int i=l; i<=r; ++i)
        {
          if(!a[i])
            ++ans;    //找到这一层的空隙数
        }
        for(int i=1; i<=n; ++i)
          if(a[i]) --a[i];
      //  debug();
      }
      printf("%lld", ans);
      return 0;

      Re:
        puts("0");
        return 0;
}

代码是之前写的有些地方应该不用特判也行(未尝试),如果有问题请各位大牛指出!最后求过+求赞 $\mathfrak{qwq}$