c/c++语言开发共享洛谷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