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


allllllan123456 (God of Computer Science)

d713. 中位数 -- UVa 10107 加強版 | 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)

d713. 中位数 -- UVa 10107 加強版 | 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)

d713. 中位数 -- UVa 10107 加強版 | From: [111.243.19.235] | 發表日期: 2021-07-05 21:49

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

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

ZeroJudge Forum