積水幾何
將非負整數陣列視為寬度為1的柱狀圖，撰寫函式，統計這樣的柱狀圖能夠積下的雨水有多少，注意，雨水只會存盤于兩邊均更高的地方，
輸入樣例：
第一行是陣列的長度，第二行是空格分隔的非負整數若干，
9
2 1 5 2 1 1 3 0 1
輸出樣例：
前述整數陣列的柱狀圖如下所示，僅在標為.的地方會存盤水，共有6個單位，
H
H
H...H
H.HH..H
HHHHHHH.H
函式回傳積水數量7，輸出由測驗程式完成，
7
函式介面定義：
int fun(int D[],int N );
/* 請在這里填寫答案 */
題解：
建立兩個陣列lmax,rmax，表示當前位置下，左側最高高度和右側最高高度，當前位置積水為res=max(min(lmax[i],rmax[i])-D[i],0)，
int min(int a,int b){
return a<b?a:b;
}
int max(int a,int b){
return a>b?a:b;
}
int fun(int D[],int N ){
int sum=0,L,R,res;
int* lmax;
int* rmax;
lmax=(int*)malloc(N*sizeof(int));
rmax=(int*)malloc(N*sizeof(int));
lmax[0]=D[0];
rmax[N-1]=D[N-1];
L=lmax[0],R=rmax[N-1];
for(int i=1;i<N;i++){
if(D[i-1]>L)
L=D[i-1];
lmax[i]=L;
}
for(int i=N-2;i>=0;i--){
if(D[i+1]>R)
R=D[i+1];
rmax[i]=R;
}
for(int i=1;i<N-1;i++){
res=max(min(lmax[i],rmax[i])-D[i],0);
sum+=res;
}
return sum;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/266010.html
標籤：其他
上一篇：解題報告（八） prufer 序列與 Cayley 公式（ACM / OI）超高質量題解
下一篇：如何實作在直播中播放音頻檔案