P1168 中位数

题目描述

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

用两个堆维护，大根堆维护较小的数里的最大值，小根对维护较大的数理的最小值，一次将每一个数插入，如果两个堆的大小差值大于1,即有一个堆中的元素并不符合实际要求，

要么大根堆里的元素维护多了一个值，要么小根堆里的元素维护多了一个值，那么这个多的值就应该被放入另一个堆中。

那么中位数就应该是元素较多的堆里的堆顶

#include<bits/stdc++.h>

using namespace std;

int n;

priority_queue<int,vector<int> >Q;//大根堆

priority_queue<int,vector<int>,greater<int> >q;//小根堆 

int main()

{

    scanf("%d",&n);

    for(int x,i=;i<=n;i++){

        scanf("%d",&x);

        if(i==){

            Q.push(x);

        }

        else {

            if(x>Q.top()) q.push(x);

            else Q.push(x);

            while(){

                int a=Q.size(),b=q.size();

                int px=(a-b)>?(a-b):(b-a);

                if(px<=) break;

                if(Q.size()>q.size()) q.push(Q.top()),Q.pop();

                else Q.push(q.top()),q.pop();

            }

        }

        if(i%) (Q.size()>q.size())?printf("%d\n",Q.top()):printf("%d\n",q.top());

    }

    return ;

}

巴特西

洛谷——P1168 中位数

P1168 中位数

题目描述

最新文章

热门文章