Running Median（对顶堆动态维护中位数）

题面:

https://ac.nowcoder.com/acm/contest/1001/D

题目大意：

多组输入，每当输入的个数为奇数时输出此时排序好的中位数。

思路：

使用优先队列的方法建立对顶堆，保持两个二叉堆的数据个数相差不大于1。 当输入个数为奇数时，输出数据个数较大的那一个的top元素。 两个二叉堆的堆顶其中之一必为中位数，因为小根堆小到大，大根堆从大到小，将堆顶放在一起相当于是将一个有序序列从中间断开，断开位置即为中位数。

代码：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> using namespace std; int s,t,n,x; int main(){ cin>>t; while(t--){ cin>>s; cin>>n; cout<<s<<" "<<((n+1)/2)<<endl; priority_queue<int,vector<int>,greater<int> > qmax; //greater表示内置类型从大到小排序，大根堆 priority_queue<int,vector<int>,less<int> > qmin; //less表示内置类型从小到大排序，小根堆 cin>>x; qmax.push(x); cout<<x<<" "; for(int i=2;i<=n;i++){ if(i%20==1) cout<<endl; scanf("%d",&x); if(qmax.top()>=x) //根据堆顶决定下一个数字去哪一个堆 qmin.push(x); else qmax.push(x); if(qmax.size()>qmin.size()+1){ //保持两个堆的数据个数之差不大于一，保持中位数在堆顶 qmin.push(qmax.top()); qmax.pop(); } else if(qmax.size()+1<qmin.size()){ qmax.push(qmin.top()); qmin.pop(); } if(i%2==1){ //为奇数个数时输出中位数 if(qmax.size()>qmin.size()) printf("%d ",qmax.top()); else printf("%d ",qmin.top()); } } cout<<endl; } return 0; }