d713 - 中位数
題目描述
題目要求我們處理一個整數序列，並在每次讀入一個新的整數後，輸出到目前為止所有整數的中位數。中位數的定義是排序後位於中間的數，如果數字個數為偶數，則取中間兩個數的和的整數部分。
解題思路
這題可以使用兩個優先佇列（堆）來解決。一個最大堆（p）用於存儲序列中較小的一半數字，一個最小堆（q）用於存儲序列中較大的一半數字。
維持兩個堆的平衡，使得它們的大小相差不超過 1。當讀入一個新的數字時，將其插入到合適的堆中。如果兩個堆的大小不平衡，則將堆頂元素從較大的堆移動到較小的堆，以保持平衡。
中位數的計算取決於序列中數字的個數是奇數還是偶數。如果數字個數為奇數，則中位數是較大堆的堆頂元素。如果數字個數為偶數，則中位數是兩個堆頂元素之和的整數部分。
程式碼中 st 變數用於區分不同的輸入情況，但邏輯上可以簡化。核心思想是維護兩個優先佇列，並在每次插入新元素後調整它們，以確保它們始終包含序列中較小和較大的一半元素。
複雜度分析
- 時間複雜度: O(N log N)，其中 N 是輸入數字的個數。因為每次插入和刪除操作都需要 O(log N) 的時間，而我們需要執行 N 次這些操作。
- 空間複雜度: O(N)，因為我們需要存儲所有輸入數字在兩個優先佇列中。
程式碼
#include <iostream>
#include <queue>
using namespace std;
long long n,st,k,m;
priority_queue <long long,vector <long long>,greater <long long> > q;//min
priority_queue <long long> p;//max
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> k){
//cout << st << " ";
if(st==0){
cout << k << "\n";
n=k;
}
else if(st==1){
cout << (k+n)/2 << "\n";
m=k;
p.push(min(n,m));//1
q.push(max(n,m));//3
}
else if(st==2){
if(k>q.top()){
q.push(k);//3 4
k=q.top();//k = 3
q.pop();// 4
}
else if(k<p.top()){
p.push(k);
k=p.top();
p.pop();
}
cout << k << "\n";
n=k;
}
else if(st%2){
//1 3 4 60
if(k>=n){
q.push(k);//4 60
m=(n+q.top())/2;
}
//2 3 4 1
else{
p.push(k);
m=(n+p.top())/2;
}
cout << m << "\n";
}
else{
if(q.size()>p.size()){
p.push(n);
if(k>q.top()){
q.push(k);
k=q.top();
q.pop();
}
p.push(k);
n=p.top();
p.pop();
}
else{
q.push(n);
if(k<p.top()){
p.push(k);
k=p.top();
p.pop();
}
q.push(k);
n=q.top();
q.pop();
}
cout << n << "\n";
}
++st;
}
}