题目描述

略

样例

略

算法1

思想是维护两个堆，一个小根堆，一个大根堆，保证大根堆中的任意元素小于小根堆，并维护两堆元素数平衡

C++ 代码

#include<algorithm>
#include<iostream>
#include<vector>
#include<functional>

using namespace std;
vector<int> mxh;
vector<int> mih;//greater<int>()

int lx=0,li=0,top;

//往最大堆填
void add_mx(int x)
{
    mxh.push_back(x);
    push_heap(mxh.begin(), mxh.end());

    //更新top,lx
    top=mxh.front();
    lx++;
}

//往最小堆填
void add_mi(int x)
{
    mih.push_back(x);
    push_heap(mih.begin(),mih.end(),greater<int>());
    //更新li
    li++;
}

//平衡两个堆的大小
void balance()
{
    if(lx-li<2&&lx>=li) return ;

    if(lx>li)//最大堆多了
    {
        pop_heap(mxh.begin(),mxh.end());
        int temp=mxh.back();
        mxh.pop_back();
        add_mi(temp);
        lx--;
    }
    else
    {

        pop_heap(mih.begin(),mih.end(),greater<int>());
        int temp=mih.back();
        mih.pop_back();
        add_mx(temp);
        li--;
    }
}


//先插入最大堆
void work(int x)
{
    if(mxh.empty())
        {
            add_mx(x);
            cout<<top<<" ";
            return ;
        }

    if(x>=top)
        add_mi(x);
    else
        add_mx(x);

    balance();

    if(lx-li==1)
    cout<<top<<" ";
}


void clear_heap()
{
    mxh.clear();
    mih.clear();
    lx=0,li=0;
}


int main()
{
    int n,tag,m;
    cin>>n;
    while(n--)
    {
        cin>>tag>>m;
        cout<<tag<<' '<<(m+1>>1)<<endl;
        for(int i=1,x;i<=m;i++)
        {
            cin>>x;
            if((i)%20==0) cout<<endl;
            work(x);
        }
        cout<<endl;
        clear_heap();
    }
}