Koios1143的筆記

Zerojudge d713

發表於 更新於 分類於

Zerojudge d713

題敘

https://zerojudge.tw/ShowProblem?problemid=d713
輸入多個數字，在輸入的同時輸出當前的序列中位數為多少(整數)

想法

觀察中位數在序列中的性質
可以發現到，中位數必定會存在於序列的中間
如果我們要動態找序列的中位數，可以利用這個性質

無論何時，我們關注的都是序列中的最中間兩個或是最中間一個數值
只要我們知道這個數值，就可以輕鬆求得中位數

利用兩個priorty queue分別記錄小於當前中位數的序列以及剩餘元素
且小於中位數的序列我們設定優先取得最大值，另一個優先取得最小值
那麼每次我們只要判斷當前元素要被放入哪個序列中，而中位數必定會在頂端

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//By Koios1143
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
priority_queue<ll,vector<ll>,greater<ll>> Mh;
priority_queue<ll> mh;
ll n;
int main(){
	while(cin>>n){
		if(mh.empty() || mh.top()>n){
			mh.emplace(n);
		}
		else{
			Mh.emplace(n);
		}
		
		if(mh.size() > Mh.size()+1){
			Mh.emplace(mh.top());
			mh.pop();
		}
		else if(Mh.size() > mh.size()+1){
			mh.emplace(Mh.top());
			Mh.pop();
		}
		
		if(mh.size() == Mh.size()){
			cout<<(mh.top()+Mh.top())/2<<'\n';
		}
		else if(mh.size() > Mh.size()){
			cout<<mh.top()<<'\n';
		}
		else{
			cout<<Mh.top()<<'\n';
		}
	}

	return 0;
}

複雜度

每次加入元素至多對priority queue做3次操作，複雜度為 $O(3nlogn)$

並且每次會做一次運算為$O(1)$

總複雜度約為$O(n^2logn)$