alan23273850 的刷題筆記
d713: 中位數
Tags: priority-queue
出處：https://zerojudge.tw/ShowProblem?problemid=d713
提交：https://zerojudge.tw/Submissions?problemid=d713&account=allllllan123456
問題：給你 $N\le200000$ 個一系列 int 整數，請你對每一個輸入，都輸出到目前為止已經輸入的數的中位數。特別地在數字個數為偶數的時候，定義中位數為中間那兩個數的總和除以 2，而且只取整數部分。
解法：這題看似需要高等資料結構，其實不然，網路上有一個廣為流傳的方法，它是把整個序列拆成左右兩半，左邊用 max-heap，開口朝右，右邊用 min-heap，開口朝左，而且兩個 heap 的 size 差距不超過 1，如此一來每次要計算中位數的時候只要把兩個 heap 的 top 抓出來檢查即可。在推入數字的時候，一樣是先檢查兩邊的 top 的大小關係來決定要推入哪個 heap，唯一要注意的是如果已經決定好要推入的 heap 它當下的 size 比另外一邊還要多，要記得先把較大 heap 的 top 取出來並推進較小 heap，再繼續原先要移入的動作。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int n; priority_queue<int> left; priority_queue<int, vector<int>, greater<int>> right;
6 left.push(INT_MIN); right.push(INT_MAX); // avoid empty queues
7 while (cin >> n) {
8 if (n < left.top()) {
9 if (left.size() > right.size()) right.push(left.top()), left.pop();
10 left.push(n);
11 } else if (n > right.top()) {
12 if (left.size() < right.size()) left.push(right.top()), right.pop();
13 right.push(n);
14 } else if (left.size() < right.size()) left.push(n);
15 else right.push(n);
16 if (left.size() > right.size()) cout << left.top() << '\n';
17 else if (left.size() < right.size()) cout << right.top() << '\n';
18 else cout << (left.top() + right.top()) / 2 << '\n';
19 }
20 return 0;
21}