每日一题4月9

题意：给你n个数，当数字个数为奇数时输出此时的中位数
思路：以第一个数作为mid值，建立一个大顶堆一个小顶堆，大于mid的加入小顶堆，小于mid 的加入大顶堆若两堆相差2个数更新mid注意格式

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <sstream>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
#include<cctype>
#include<cstring>
#include<cstdlib>
#define MAXX 100005
#define SIS std::ios::sync_with_stdio(false)
#define ll long long
#define INF 0x3f3f3f3f
//#include<bits/stdc++.h>
using namespace std;
const int MAX =2e5+20;
const double PI = 3.14159265359;

int main()
{
    int n,m,t;
    scanf("%d",&t);
    while(t--)
    {
        priority_queue<int> big;
        priority_queue<int ,vector<int>,greater<int> > small;
        scanf("%d %d",&n,&m);
        int mid,sum,x;
        printf("%d %d\n",n,(m+1)/2);

        for(int i=1;i<=m;i++)
        {
           scanf("%d",&x);
            if(i==1)
            {
                sum=1;mid=x;
                printf("%d ",mid);
                continue;
            }
            if(x<mid)
                big.push(x);
            else
                small.push(x);
            if(big.size()-small.size()==2)
            {
                small.push(mid);
                mid=big.top();
                big.pop();
            }
            else if(small.size()-big.size()==2)
            {
                big.push(mid);
                mid=small.top();
                small.pop();
            }
            if(i%2!=0)
            {
                sum++;
                if(sum%10!=0)
                    printf("%d ",mid);
                else
                    printf("%d\n",mid);
            }
        }
        if(sum%10!=0)
            printf("\n");

    }
    return 0;

}