題目?

依次讀入一個(gè)整數(shù)序列，每當(dāng)已經(jīng)讀入的整數(shù)個(gè)數(shù)為奇數(shù)時(shí)，輸出已讀入的整數(shù)構(gòu)成的序列的中位數(shù)。

輸入格式

第一行輸入一個(gè)整數(shù)?P，代表后面數(shù)據(jù)集的個(gè)數(shù)，接下來若干行輸入各個(gè)數(shù)據(jù)集。

每個(gè)數(shù)據(jù)集的第一行首先輸入一個(gè)代表數(shù)據(jù)集的編號(hào)的整數(shù)。

然后輸入一個(gè)整數(shù)?M，代表數(shù)據(jù)集中包含數(shù)據(jù)的個(gè)數(shù)，M?一定為奇數(shù)，數(shù)據(jù)之間用空格隔開。

數(shù)據(jù)集的剩余行由數(shù)據(jù)集的數(shù)據(jù)構(gòu)成，每行包含?10?個(gè)數(shù)據(jù)，最后一行數(shù)據(jù)量可能少于?10?個(gè)，數(shù)據(jù)之間用空格隔開。

輸出格式

對于每個(gè)數(shù)據(jù)集，第一行輸出兩個(gè)整數(shù)，分別代表數(shù)據(jù)集的編號(hào)以及輸出中位數(shù)的個(gè)數(shù)（應(yīng)為數(shù)據(jù)個(gè)數(shù)加一的二分之一），數(shù)據(jù)之間用空格隔開。

數(shù)據(jù)集的剩余行由輸出的中位數(shù)構(gòu)成，每行包含?10?個(gè)數(shù)據(jù)，最后一行數(shù)據(jù)量可能少于?10?個(gè)，數(shù)據(jù)之間用空格隔開。

輸出中不應(yīng)該存在空行。

數(shù)據(jù)范圍

1≤P≤1000
1≤M≤99999
所有?M?相加之和不超過?5×1e5

輸入樣例：

3 
1 9 
1 2 3 4 5 6 7 8 9 
2 9 
9 8 7 6 5 4 3 2 1 
3 23 
23 41 13 22 -3 24 -31 -11 -8 -7 
3 5 103 211 -311 -45 -67 -73 -81 -99 
-33 24 56

輸出樣例：

1 5
1 2 3 4 5
2 5
9 8 7 6 5
3 12
23 23 22 22 13 3 5 5 3 -3 
-7 -3

思路

? ? ? ? 使用一個(gè)大根堆一個(gè)小根堆動(dòng)態(tài)維護(hù)一個(gè)對頂堆，保持在放入奇數(shù)個(gè)數(shù)據(jù)時(shí)，下面的堆比上面的堆多1個(gè)元素，如下圖所示。

當(dāng)總元素個(gè)數(shù)為奇數(shù)的時(shí)候，輸出down.top()，即為當(dāng)前所有元素的中位數(shù)。?

代碼

#include<bits/stdc++.h>
using namespace std;void solve()
{int n,m;cin >> n >> m;cout << n << " " << (m + 1) / 2 << endl;priority_queue<int, vector<int>,less<>> down;priority_queue<int, vector<int>,greater<>> up;int cnt = 0;for(int i = 1; i <= m; i ++){int x;cin >> x;if(down.empty() || x <= down.top()) down.push(x);else up.push(x);if(down.size() > up.size() + 1) up.push(down.top()),down.pop();if(up.size() > down.size()) down.push(up.top()),up.pop();if(i % 2){cout << down.top() << " ";if(++ cnt % 10 == 0) cout << endl;}}if(cnt % 10) cout << endl;
}int main()
{int T;cin >> T;while(T --)solve();return 0;
}

難度：中等

時(shí)/空限制：2s / 256MB

總通過數(shù)：9036

總嘗試數(shù)：22991

來源：《算法競賽進(jìn)階指南》

算法標(biāo)簽 堆https://www.acwing.com/problem/search/1/?search_content=%E5%A0%86

題目來自：?106. 動(dòng)態(tài)中位數(shù) - AcWing題庫