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


yes51851823@gmail.com (wseds)

School : 國立花蓮高級工業職業學校
ID : 108813
IP address : [111.243.214.89]
Last Login :
2021-10-01 22:27:22
f174. m6a2-蛋糕(Cake) -- TOI練習賽2020年6月潛力組 | From: [114.44.204.99] | Post Date : 2020-09-25 22:24

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

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

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

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

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

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


yes51851823@gmail.com (wseds)

School : 國立花蓮高級工業職業學校
ID : 108813
IP address : [111.243.214.89]
Last Login :
2021-10-01 22:27:22
f174. m6a2-蛋糕(Cake) -- TOI練習賽2020年6月潛力組 | From: [111.243.204.18] | Post Date : 2020-11-05 23:15

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

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

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

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

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


O(n logn)

 
ZeroJudge Forum