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


yes51851823@gmail.com (wseds)

學校 : 國立花蓮高級工業職業學校
編號 : 108813
來源 : [114.36.253.126]
最後登入時間 ：
2025-08-25 16:32:53
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.253.126]
最後登入時間 ：
2025-08-25 16:32:53
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