Running Median（蒟蒻解法）

（个人感觉这题最难的地方是看懂题目）ps：没想到有人用sort维护都能ac，可能因为这个加强了数据吧

Solution

题意是：输入奇数个数的时候输出此时输入的数的中间值（本蒟蒻看成了输入的数是奇数），因为可能输入的数有相同的所以可以用multiset保存输入的数，对于每次输出可用迭代器寻找值为中间的数即可

做完了这题可以去试试 poj 3784 也是对顶堆的模板题

code(前解法)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e8
const int mod = 1e9+7;
const int maxn = 10005;
#define iss ios::sync_with_stdio(false)
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
multiset<int> q;
int main(){
    int p,ii,num;
    p = read();
    int temp;
    while(p--){
        ii = read();num = read();
        q.clear();//因为是多组，这里要清空
        queue<int> qq;
        for(int i = 1 ; i <= num ;++i){
            temp = read();
            q.insert(temp);
            if(i&1){
                multiset<int>::iterator it = q.begin();//迭代器寻找中间的数
                for(int j = 0 ; j < i/2 ;++j) ++it;
                qq.push(*it);
            }
        }
        cout<<ii<<" "<<num/2+1<<endl;
        int i;
        for( i = 0 ; !qq.empty() ;++i){
            if(i%10==0) cout<<qq.front();
            else cout<<" "<<qq.front();
            qq.pop();
            if(i%10==9) cout<<endl;//每10个数要换行
        }
        if(i%10!=9) cout<<endl;    //如果for循环的最后一个数没有换行，这里就换行
    }
}

加强数据发现不能a，那蒟蒻只能用优先队列了

开两个对顶堆，大根堆 q1 存序列中从小到大 num/2+1个数，小根堆 q1 存从大到小 num/2个数（题目保证num为奇数）

对于输入的数temp大于中位数的放在大根堆，小于的放在小根堆。接下来就是维护长度了，如果大根堆长度大于小根堆加一那就把大根堆最大的丢进小根堆，反过来一样是这样。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e8
const int mod = 1e9+7;
const int maxn = 1e6+5;
#define iss ios::sync_with_stdio(false)
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
priority_queue<int> q1;
priority_queue<int, vector<int>,greater<int> > q2;//greater<int>表示q2里元数小的优先级高
int main(){
    int p,temp;
    p = read();
    while(p--){
        while(!q1.empty()) q1.pop();//清空
        while(!q2.empty()) q2.pop();
        int id,num;
        id = read();
        num = read();
        printf("%d %d\n",id,(num>>1)+1);
            temp = read();
            printf("%d ",temp);
            q1.push(temp);//因为temp是和q1.top()比较，先把第一个数塞进去就不用判断是否为空了
        for(int i = 2 ; i <= num ;++i){
            temp = read();
            if(temp <= q1.top()) q1.push(temp);
            else q2.push(temp);
            if(q1.size() > q2.size() + 1){
                q2.push(q1.top());q1.pop();
            }
            if(q2.size() > q1.size()){
                q1.push(q2.top());q2.pop();
            }
            if(i&1) printf("%d ",q1.top());
            if((i%20)==0) puts("");
        }
        if(num%20!=0) puts("");
    }
}