Running Median题解

题意思 每次输入一个数字 然后当为奇数个的时候就输出前面奇数个的中位数，注意输出格式啊，卡死人。
首先，我们可以傻一点，是不是每次输入一个树就存一个数组 然后排序，然后直接a[i/2+1],是不是就是改该中位数啦，但是每次这样处理肯定T，然后既然我们知道要排序，是不是就可以取优化他啦，这儿就送来了优先队列（堆），嘿嘿，是不是就有一点头绪啦，我们建立两个堆，一个大根堆，一个小根堆。然后第一个数进入小根堆，然后每次比较下一个数和小根堆的大小，比他大 ，就去大根堆，反之，就是去小根堆，既然奇数输出中位数，然后我们要分配两个堆的数字，既然是奇数，那么必然是大小跟堆size相差1，如果大于一 是不是我们就应该调到另一个堆去，那么是不是每次i&1就可以啦，那个堆大 就输出那个堆的top；

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
priority_queue<int>q1;///大根堆，存小数
priority_queue<int,vector<int>,greater<int> >q2;///小根堆，存大数
int main()
{
    fio;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        while(!q1.empty()) q1.pop();
        while(!q2.empty()) q2.pop();
        int m,n;
        scanf("%d%d",&m,&n);
       printf("%d %d\n",m,(n+1)/2);
        int x;
        scanf("%d",&x);
        q1.push(x);
        printf("%d ",x);
        for(int i=2;i<=n;i++)
        {
            scanf("%d",&x);
            if(x<=q1.top()) q1.push(x);
            else
                q2.push(x);
            int len1=q1.size();
            int len2=q2.size();
            if(len1-len2>1)
            {
                q2.push(q1.top());
                q1.pop();
            }
            else if(len2-len1>1)
            {
                q1.push(q2.top());
                q2.pop();
            }
            if(i&1)
            {
                len1=q1.size();
                len2=q2.size();
                if(len1>len2)
                   printf("%d ",q1.top());
                else
                printf("%d ",q2.top());
                     if(i % 20 == 19 && i != n) printf("\n");

            }
        }
        printf("\n");
    }


    return 0;
}

注意，不要开longlong，要爆空间，我使用cin超时，我tm心态蹦了呀。