#24375: 想法


fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.217.8]
最後登入時間 :
2024-04-13 22:06:23
c364. 我鄙視你 -- 106 學年度第一次 CRC 附電盃程式設計團體賽 | From: [61.230.56.79] | 發表日期 : 2021-02-10 11:10

這題通過率有點低,來寫個解題報告好了

用到的陣列: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

 
#37265: Re: 想法


fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.217.8]
最後登入時間 :
2024-04-13 22:06:23
c364. 我鄙視你 -- 106 學年度第一次 CRC 附電盃程式設計團體賽 | From: [1.161.138.172] | 發表日期 : 2023-08-29 00:39

更新連結

https://mousecoding.blogspot.com/2023/08/zerojudge-c364.html

 
ZeroJudge Forum