P1168 中位数（对顶堆）

ruoye123456 / 2024-09-17 / 原文

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}

void solve()
{
	priority_queue<int> q_B;
	priority_queue<int,vector<int>,greater<int>> q_S;
	int n;
	cin>>n;
	//用小根堆维护比根节点大的一半节点,大根堆维护比小根堆根节点小的
	vector<int> a(n);
	for(int i=0;i<n;++i) cin>>a[i];
	q_S.push(a[0]);
	cout<<a[0]<<'\n';
	
	for(int i=1;i<n;++i)
	{
		//当i为奇数时插入大顶堆,偶数时插入小顶堆
		if(i&1)
		{
			if(a[i]<=q_S.top())
			{
				q_B.push(a[i]);
			}
			else
			{
				q_B.push(q_S.top());
				q_S.pop();
				q_S.push(a[i]);
			}
		}
		else
		{
			if(a[i]>=q_B.top())
			{
				q_S.push(a[i]);
			}
			else
			{
				q_S.push(q_B.top());
				q_B.pop();
				q_B.push(a[i]);
			}
			cout<<q_S.top()<<'\n';
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}