题目地址: 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
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605862.html