边输入边排序（二分插入）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n;
vector<int> a;
int main(int argc, char **argv){
	cin >> n;
	for (int i = 1;i <= n;i++){
		int x;
		cin >> x;
		auto it = lower_bound(a.begin(),a.end(),x);
		a.emplace(it,x);
		// for (int j = 0;j < a.size();j++){
		// 	cout << a[j] << " ";
		// }
		// cout << endl;
		if (i & 1){
			cout << a[(i >> 1)] << endl;
		}
	}
	return 0;
}

对顶堆写法（这个偏过程，简洁版看这里）

#include <bits/stdc++.h>
using namespace std;
template<typename tp>
class Heap{
	private:
		vector<tp> hp = {0};
		bool (*cmp)(tp,tp);
		void down(int p){
			int n = size();
			while (p << 1 <= n){
				int t = p << 1;
				if (t < n && (*cmp)(hp[t + 1],hp[t])) t++;
				if ((*cmp)(hp[t],hp[p])){
					swap(hp[t],hp[p]);
					p = t;
				}else	break;
			}
		}
		void up(int p){
			while (p > 1 && (*cmp)(hp[p],hp[p >> 1])){
				swap(hp[p],hp[p >> 1]);
				p >>= 1;
			}
		}
		tp get(int p){
			return hp[p];
		}
	public:
		Heap(){
			cmp = [](tp a,tp b){return a > b;};
		}
		Heap(bool (*f)(tp,tp)){
			cmp = f;
		}
		int size(){
			return hp.size() - 1;
		}
		void ins(tp x){
			hp.emplace_back(x);
			up(size());
		}
		void rm(int p){
			swap(hp[p],hp[size()]);
			hp.pop_back();
			down(p);
		}
		void pop(){
			rm(1);
		}
		tp top(){
			return get(1);
		}
		tp operator[](int p){
			return get(p);
		}
};

bool cmp(int a,int b){
	return a < b;
}
Heap<int> hb,hs(cmp);
int main(int argc, char **argv){
	int n;
	cin >> n;
	int x;
	cin >> x;
	hs.ins(x);
	printf("%d\n",x);
	for (int i = 2;i <= n;i++){
		cin >> x;
		if (hs.size() == hb.size()){
			if (x >= hb.top())	hs.ins(x);
			else{
				hs.ins(hb.top());
				hb.pop();
				hb.ins(x);
			}
		}
		else{
			if (x <= hs.top())	hb.ins(x);
			else{
				hb.ins(hs.top());
				hs.pop();
				hs.ins(x);
			}
		}
		if (i & 1)	printf("%d\n",hs.top());
	}
	return 0;
}

更简洁的中位对顶堆写法

#include<bits/stdc++.h>
using namespace std;
template<typename T>
class d_heap
{
	private:
		#define pq priority_queue
		pq<T>big;
		pq<T,vector<T>,greater<T> >small;
		#undef pq
		void ph()//左右平衡 
		{
			if(big.size()<small.size())
				big.push(small.top()),small.pop();
			if(big.size()-small.size()>1)
				small.push(big.top()),big.pop();
		}
	public:
		void push(T x)
		{
			if(small.size() && x>small.top())small.push(x);
			else big.push(x);
			ph();
		}
		T top()
		{
			return big.top();
		}
};
d_heap<int>q;
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;cin>>x;
		q.push(x);
		if(i%2)
			cout<<q.top()<<"\n";
	}
	return 0;
}

vector+二分写法

#include<bits/stdc++.h>
using namespace std;
vector<int>v;
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;cin>>x;
		v.insert(upper_bound(v.begin(),v.end(),x),x);
		if(i%2)
			cout<<v[v.size()/2]<<"\n";
	}
	return 0;
}

这道题只用一个堆是不现实的因为中位数在数组中间，没办法用堆查询和运算，那就两个，一个存小半边一个存大半边中位数就是小半边的堆顶元素

我看完题解才知道可以二分暴力排序

不说了，上代码，我自认为码风还行

#include<bits/stdc++.h>
using namespace std;
int n;
priority_queue<int> maxh;
//存小的那一半 
priority_queue<int,vector<int>,greater<int> > minh;
//存大的那一半 
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		(maxh.empty()||a<=maxh.top())?maxh.push(a):minh.push(a);
		//小于中间的就去小半边，反之去大半边 
		if(maxh.size()>minh.size()+1){
			/*因为中位数取小半边的最大，
			所以小半边大小不能多于大半边大小加一*/ 
			minh.push(maxh.top());
			maxh.pop();
		}else if(minh.size()>maxh.size()){
			//使两边大小差值恰好保持在1
			maxh.push(minh.top());
			minh.pop();
		}
		if(i&1) cout<<maxh.top()<<"\n";//输出即可 
	}
	return 0;
}