洛谷P1318 积水面积

题目地址: https://www.luogu.org/problemnew/show/p1318

题意简述

给出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;
}

代码是之前写的有些地方应该不用特判也行（未尝试）qwq