题目链接
https://www.luogu.org/problemnew/show/P1168
解题思路
这个题就是求中位数，但是暴力会tle，所以我们用一种O(nlogn)的算法来实现。
这里用到了两个堆，一个是大根堆，一个是小根堆，大根堆中的数总是小于小根堆中的数，且两个堆之间的数量最多差一。
见图（自己手画的，不太美观，请见谅）：
就是这个样子，让两个堆的堆顶凑到一块比较容易理解。
就这样，每一次的答案就是元素个数较多的堆的堆顶。
AC代码
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 using namespace std; 5 const int maxn=100005; 6 int n; 7 priority_queue<int> q1; 8 priority_queue<int,vector<int>,greater<int> > q2; 9 int main(){ 10 cin>>n; 11 for(int i=1;i<=n;i++){ 12 int a; 13 scanf("%d",&a); 14 int s1=q1.size(); 15 int s2=q2.size(); 16 if(s1==0) q1.push(a); 17 else{ 18 int a1=q1.top(); 19 if(a<=a1){ 20 q1.push(a); 21 s1++; 22 } 23 else{ 24 q2.push(a); 25 s2++; 26 } 27 } 28 while(s1-s2>1){ 29 q2.push(q1.top()); 30 q1.pop(); 31 s1--; 32 s2++; 33 } 34 while(s2-s1>=1){ 35 s2--; 36 s1++; 37 q1.push(q2.top()); 38 q2.pop(); 39 } 40 if(i%2==1) printf("%d\n",q1.top()); 41 } 42 return 0; 43 }