P1168 中位数

题目描述

给出一个长度为 $NN的非负整数序列A_iAi，对于所有1 ≤ k ≤ (N + 1) / 21≤k≤(N+1)/2，输出A_1, A_3, …, A_{2k - 1}A1,A3,…,A2k−1的中位数。即前1,3,5,…1,3,5,…个数的中位数。$

输入输出格式

输入格式：

第

第 $22行包含NN个非负整数A_i (A_i ≤ 10^9)Ai(Ai≤109)。$

输出格式：

共 $2(N+1)/2行，第ii行为A_1, A_3, …, A_{2k - 1}A1,A3,…,A2k−1的中位数。$

输入输出样例

输入样例#1：复制

7
1 3 5 7 9 11 6

输出样例#1：复制

1
3
5
6


比较巧妙的方法使用对顶堆  维护左边的数（也就是小一点的数)用大顶堆   另外一边用小顶堆

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s)
#define ll long long
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define pb push_back
#define inf 0x3f3f3f3f
#define CLR(A,v)  memset(A,v,sizeof A)
typedef pair<int,int>pii;
//////////////////////////////////
const int N=2e6+10;

priority_queue<int>q1;
priority_queue<int,vector<int> ,greater<int> >q2;
int n,x;
int main()
{
    RI(n);
    RI(x);q1.push(x);
    cout<<x<<endl;
    rep(i,2,n)
    {
        RI(x);
        if(x>q1.top())q2.push(x);else q1.push(x);

        int q1len=q1.size(),q2len=q2.size();
        while(abs(q1len-q2len)>1)
        {
            if(q1.size()>q2.size())
            q2.push(q1.top()),q1.pop();
            else q1.push(q2.top()),q2.pop();
            q2len=q2.size();q1len=q1.size();
        }
        if(i%2) printf("%d
",q1.size()>q2.size()?q1.top():q2.top());
    }

    return 0;
}

View Code