發表新討論
#25536: max heap + min heap


allllllan123456 (God of Computer Science)

學校 : 國立臺灣大學
編號 : 13732
來源 : [140.109.20.138]
最後登入時間 ：
2021-07-08 17:41:52
d713. 中位数 -- UVa10107加強版 | From: [125.231.121.9] | 發表日期 : 2021-05-30 15:45

這題比較常見且簡單的方法是同時維護兩個 heap，把整個數列切兩半，左半邊是 max heap，右半邊是 min heap，開口朝中間，隨時維持兩邊大小 "幾乎" 相等，那麼中位數就是兩個 heap 的 top 的平均了。

 
#25924: Re:max heap + min heap


allllllan123456 (God of Computer Science)

學校 : 國立臺灣大學
編號 : 13732
來源 : [140.109.20.138]
最後登入時間 ：
2021-07-08 17:41:52
d713. 中位数 -- UVa10107加強版 | From: [125.231.133.241] | 發表日期 : 2021-07-04 18:47

這題比較常見且簡單的方法是同時維護兩個 heap，把整個數列切兩半，左半邊是 max heap，右半邊是 min heap，開口朝中間，隨時維持兩邊大小 "幾乎" 相等，那麼中位數就是兩個 heap 的 top 的平均了。


https://alan23273850.github.io/Online-Judge-Problems/zerojudge/d713/

 
#25935: Re:max heap + min heap


fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.253.147]
最後登入時間 ：
2024-10-03 15:39:22
d713. 中位数 -- UVa10107加強版 | From: [111.243.19.235] | 發表日期 : 2021-07-05 21:49

這方法妙！ 原本是用vector每次都binary search找中位數後在insert，insert很花時間但是剛剛好這題能過(0.9s)

用大大的方法後壓到8x毫秒

 
ZeroJudge Forum