中位数

题目描述

给出一个长度为 $N的非负整数序列A_i，对于所有1 ≤ k ≤ (N + 1) / 2，输出A1,A3,…,A2k−1的中位数。即前1,3,5,…个数的中位数。$

输入输出格式

输入格式：

第

第 $2行包含N个非负整数A_i (A_i ≤ 10^9)。$

输出格式：

共

输入输出样例

输入样例#1：

7
1 3 5 7 9 11 6

输出样例#1：

说明

对于

$本题数据规模较大，故不能正常枚举求中位数，但是通过对堆的性质分析，可以运用对头堆求解，更进一步，STL中vector与upper_bound结合同样可以求解。$

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<vector>
 5 #include<cmath>
 6 using namespace std;
 7 const int M=100005;
 8 int n;
 9 vector <int> q;
10 inline int get(){
11     char c=getchar();
12     int f=1;
13     while (c>'9'||c<'0') {
14         if (c=='-') f=-1;
15         c=getchar();
16     }
17     int res=0;
18     while (c>='0'&&c<='9') {
19         res=(res<<3)+(res<<1)+c-'0';
20         c=getchar();
21     }
22     return res*f;
23 }
24 int main(){
25     n=get();
26     for (int i=1;i<=n;i++){
27         int a=get();
28         q.insert(upper_bound(q.begin(),q.end(),a),a);
29         if (i%2==1) printf ("%d ",q[(i-1)/2]);
30     }
31     return 0;
32 }

堆版本（某大佬的）：

 1 #include <algorithm>
 2 #include <cstring>
 3 #include <queue>
 4 #include <cstdio>
 5 using namespace std;
 6 
 7 priority_queue<int, vector<int>, greater<int> > q1;
 8 priority_queue<int, vector<int>, less<int> > q2;
 9 int check=1,n,m,middle,k;
10 
11 void add(int x){
12     if(q1.empty()){
13         q1.push(x);
14     }
15     else if(x>q1.top()){
16         q1.push(x);
17     }
18     else{
19         q2.push(x);
20     }
21     while(q1.size()<q2.size()){
22         q1.push(q2.top());
23         q2.pop(); 
24     }
25     while(q1.size()>q2.size()+1){
26         q2.push(q1.top());
27         q1.pop();
28     }
29 }
30 
31 int main() {
32     scanf("%d",&n);
33     for(int i=1;i<=n;i++) {
34         scanf("%d",&m);
35         add(m);
36         if(i%2)
37             printf("%d ",q1.top());
38     }
39     return 0;
40 }