#25536: max heap + min heap
allllllan123456
(God of Computer Science)
學校
:
國立臺灣大學
編號 : 13732
來源 : [140.109.20.138]
最後登入時間 ：
2021-07-08 17:41:52
這題比較常見且簡單的方法是同時維護兩個 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
這題比較常見且簡單的方法是同時維護兩個 heap，把整個數列切兩半，左半邊是 max heap，右半邊是 min heap，開口朝中間，隨時維持兩邊大小 "幾乎" 相等，那麼中位數就是兩個 heap 的 top 的平均了。
https://alan23273850.github.io/Online-Judge-Problems/zerojudge/d713/
#25935: Re:max heap + min heap
這方法妙！ 原本是用vector每次都binary search找中位數後在insert，insert很花時間但是剛剛好這題能過(0.9s)
用大大的方法後壓到8x毫秒