P1318 積水面積

題目描述

一組正整數(shù)，分別表示由正方體迭起的柱子的高度。若某高度值為x，表示由x個正立方的方塊迭起（如下圖，0<=x<=5000）。找出所有可能積水的地方（圖中藍(lán)色部分），統(tǒng)計它們可能積水的面積總和（計算的是圖中的橫截面積。一個立方體的位置，為一個單位面積）。

如圖：柱子高度變化為 0 1 0 2 1 2 0 0 2 0

圖中藍(lán)色部分為積水面積，共有6個單位面積積水。

輸入輸出格式

輸入格式：

?

兩行，第一行n,表示有n個數(shù)(3<=n<=10000)。第2行連續(xù)n個數(shù)表示依次由正方體迭起的高度，保證首尾為0。

?

輸出格式：

?

一個數(shù)，可能積水的面積。

?

輸入輸出樣例

輸入樣例#1：?復(fù)制 10 0 1 0 2 1 2 0 0 2 0 輸出樣例#1：?復(fù)制 6
#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std; int n,maxn,ans; int a[5010],l[5010],r[5010]; int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);maxn=max(maxn,a[i]); }for(int i=1;i<=n;i++)l[i]=max(a[i],l[i-1]);for(int i=n;i>=1;i--)r[i]=max(a[i],r[i+1]);for(int i=1;i<=maxn;i++){for(int j=1;j<=n;j++)if((l[j]>=i)&&(r[j]>=i)&&(a[j]<i)) ans++;}cout<<ans; } /* 12 0 3 2 0 0 2 0 3 1 1 2 0 */

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/cangT-Tlan/p/9649815.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 P1318 积水面积的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。