Running Median

题意:输出数组 的中位数
懵逼的题解:每次数组 排序...
我不知道为什么这个能过,
时间复杂度:
我怎么算这个时间复杂度也会炸的呀.......

//ac code
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int p;
    cin>>p;
    while(p--)
    {
        int t,m;
        int ans=0;
        cin>>t>>m;
        int a[m+5];
        cout<<t<<" "<<m/2+1<<'\n';
        for(int i=0;i<m;i++) cin>>a[i];
        for(int i=0;i<m;i++)
        {
            if((i+1)%2!=0)
            {
                sort(a,a+i+1);
                if(ans==0) cout<<a[i/2];
                else cout<<" "<<a[i/2];
                ans++;
                if(ans==10)
                {
                    ans=0;
                    cout<<'\n';
                }
            }
        }
        if(p!=0)
            cout<<'\n';
    }
    return 0;
}

正常的题解:建立最大堆,最小堆(可以直接写优先队列,不用手动建堆)
把每次输入的元素压入最大堆和最小堆中,然后进行两个堆的调整,如果两个堆的堆顶值不同,那么连个堆堆顶值全部弹出,然后再交换压入,最后可以达到的效果是
大根堆存储的是数组
小根堆存储的是数组
其中
以上数字为调整后的数字大小,只用作举例说明,并且大根堆小根堆的数组长度相同,而且此处假设原数组为
堆是什么呢 https://baike.baidu.com/item/%E5%A0%86/20606834?fr=aladdin ---来自百度百科
时间复杂度:
正常一点可以过的时间复杂的

#include<bits/stdc++.h>
using namespace std;
int main() {
    int T;
    cin >> T;
    while(T--) {
     priority_queue<int,vector<int>, greater<int> > que_1; //小顶堆
priority_queue<int> que_2;
        int kk, n, x;
        cin >> kk >> n;
        cout << kk << ' ' << (n+1)/2 << endl;
        for(int i = 1; i <= n; i++) {
            cin >> x;
            que_1.push(x);
            que_2.push(x);
            if(i%2==0)
                continue;
            while(que_1.top() != que_2.top()) {
                int a = que_1.top();
                int b = que_2.top();
                que_1.pop(), que_2.pop();
                que_1.push(b);
                que_2.push(a);
            }
            cout << que_2.top() << ' ';
            if(((i+1)/2)%10 == 0)
                cout << "\n";
            else if((n%2==1&&i==n) || (n%2==0&&i==n-1))
                cout << "\n";
        }

    }
return 0;
}

上面的第一个题解更新之前能过,现在数据已经更新