跳到主要内容

Chalkboard Median

· 阅读需 1 分钟

动态中位数模板，对顶堆维护即可

AC代码
Details
#include<bits/stdc++.h>
using namespace std;
#define QAQ return 
#define QWQ return 0;
#define ll long long
#define pii pair< int,int >


priority_queue< int > small;
priority_queue< int,vector< int >,greater< int > > big;

inline void add( int x )
{
	if( x >= small.top() ) big.push( x );
	else                   small.push( x );
	if( small.size() == big.size()+2 ) big.push( small.top() ), small.pop();
	if( big.size() == small.size()+1 ) small.push( big.top() ), big.pop();
}

int main()
{
//	freopen( "txt.in","r",stdin );
//	freopen( "txt.out","w",stdout );
	ios::sync_with_stdio( false );
	cin.tie( nullptr ), cout.tie( nullptr );
	int x, y;
	cin>>x;
	small.push( x );
	int q;
	for( cin>>q;q;q-- )
	{
		cin>>x>>y;
		add( x );
		add( y );
		cout<<small.top()<<"\n";
	}
	QWQ	 
}

时间复杂度：O(n)O(n)