發表新討論
#22694: 只要找到每個數前K-1個裡面最小的


yes51851823@gmail.com (wseds)

學校 : 國立花蓮高級工業職業學校
編號 : 108813
來源 : [114.36.212.168]
最後登入時間 ：
2024-10-17 21:35:26
f174. m6a2-蛋糕(Cake) -- TOI練習賽2020年6月潛力組 | From: [114.44.204.99] | 發表日期 : 2020-09-25 22:24

我們可以先利用輸入建立前綴和的表

接著只要掃一遍這陣列　對於每個數找其出前K-1個數中最小的來相減即為這K個數中所能達到的最大值

找出所有連續K個數中所能達到的最大值即為正解

(我們可以利用map的自動排序且可記錄重複數字的特性來尋找前K-1個數中的最小值)

就可以在大約O(N)的複雜度完成

 
#23307: Re:只要找到每個數前K-1個裡面最小的


yes51851823@gmail.com (wseds)

學校 : 國立花蓮高級工業職業學校
編號 : 108813
來源 : [114.36.212.168]
最後登入時間 ：
2024-10-17 21:35:26
f174. m6a2-蛋糕(Cake) -- TOI練習賽2020年6月潛力組 | From: [111.243.204.18] | 發表日期 : 2020-11-05 23:15

我們可以先利用輸入建立前綴和的表

接著只要掃一遍這陣列　對於每個數找其出前K-1個數中最小的來相減即為這K個數中所能達到的最大值

找出所有連續K個數中所能達到的最大值即為正解

(我們可以利用map的自動排序且可記錄重複數字的特性來尋找前K-1個數中的最小值)

就可以在大約O(N)的複雜度完成


O(n logn)

 
ZeroJudge Forum