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


yes51851823@gmail.com (wseds)

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)

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