链接
http://poj.org/problem?id=3784
题意
给出一个长度为奇数的序列，输出前 $1,3,5,…,m$ 个数的中位数
思路
对顶堆
建立一个小根堆和大根堆
如果当前数比小根堆堆顶大，插入小根堆
如果当前数比小根堆堆顶小，插入大根堆
大根堆堆顶是始终小于小根堆堆顶的
当已经插入的个数为奇数时，我们要保证大根堆里的数比小根堆里的数少一个
如果大根堆里的数多，则把大根堆堆顶插入小根堆
如果小根堆里的数多，则把小根堆堆顶插入大根堆
所以小根堆堆顶就是中位数
代码
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
| #include<bits/stdc++.h>
using namespace std;
int a[10000];
priority_queue<int,vector<int>,greater<int> >q1;
priority_queue<int>q2;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--) {
int t,n;
cin>>t>>n;
while(q1.size()) q1.pop();
while(q2.size()) q2.pop();
for(int i=1;i<=n;i++) cin>>a[i];
cout<<t<<" "<<(n+1)/2<<endl;
for(int i=1;i<=n;i++) {
if(!q1.size()||a[i]>q1.top()) q1.push(a[i]);
else q2.push(a[i]);
if(i&1) {
if(q1.size()-1>q2.size()) q2.push(q1.top()),q1.pop();
if(q2.size()+1>q1.size()) q1.push(q2.top()),q2.pop();
}
if(i&1) cout<<q1.top()<<" ";
if(i%20==0||i==n) cout<<endl;
}
}
return 0;
}
|