這題通過率有點低,來寫個解題報告好了
用到的陣列:h(紀錄身高)、prefix(紀錄前綴和)、dp(dp[i]代表第i個人比左邊(或右邊)高的人數)、ans(紀錄最後答案)
以範例測資舉例:
5 140 150 170 180 160
首先前從左邊往右邊更新
140因為是最左邊的人,所以左邊沒人,dp[0] = 0,ans[0] = 0
150左邊有人,而且身高比140高,所以將指標移到140左邊,但是已經超過陣列了,所以結束。dp[1] = 1,ans[1] = prefix[1 - 1] - prefix[-1](定義為0) = 140
170比左邊的150高,且150贏的人數為1(dp[1] = 1),所以170不用和140比較就知道170比較高(150>140、170>140),dp[2] = 2,ans[2] = prefix[2 - 1] - prefix[-1] = 290
180也是同上,dp[3] = 3,ans[3] = prefix[3 - 1] - prefix[-1] = 460
160因為左邊的人比他高,所以dp[4] = 0,ans[4] = 0
接下來換從右邊開始,方法跟左邊一樣
算完直接把ans印出來就好了
用C++的建議不要用vector,因為偏慢,可能會超時
程式碼連結:https://66lemon66.blogspot.com/2021/01/zerojudge-c364-c.html