【洛谷 1168】动态中位数

题目描述

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

输入输出格式

输入格式： 第11行为一个正整数NN，表示了序列长度。

第22行包含NN个非负整数A_i (A_i ≤ 10^9)A i ​ (A i ​ ≤10 9 )。

输出格式： 共(N + 1) / 2(N+1)/2行，第ii行为A_1, A3, …, A{2k - 1}A 1 ​ ,A 3 ​ ,…,A 2k−1 ​ 的中位数。

输入输出样例

输入样例#1： 复制 7 1 3 5 7 9 11 6 输出样例#1： 复制 1 3 5 6 说明

对于20\%20%的数据，N ≤ 100N≤100；

对于40\%40%的数据，N ≤ 3000N≤3000；

对于100\%100%的数据，N ≤ 100000N≤100000。

题解：emmm一道二叉堆。第一次接触堆，好吃力嘤嘤嘤。一个大根堆，一个小根堆。大的存小数据，小的存大数据。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
typedef long long ll;
using namespace std;
priority_queue<int, vector<int>, greater<int> > q1;//小根堆,存较大数 
priority_queue<int, vector<int>, less<int> > q2; //大根堆，存较小数 
int n,x;
void work(int x){
    if(q1.empty()==1) q1.push(x);
    else 
    if(x>q1.top()) q1.push(x);
    else q2.push(x);
    
    while(q1.size()<q2.size()){
        q1.push(q2.top());
        q2.pop();
    } 
    while(q1.size()>q2.size()){
        q2.push(q1.top());
        q1.pop();
    } 
}

int main(){
    freopen("1168.in","r",stdin);
    freopen("1168.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        work(x);
        if(i%2==1) cout<<q1.top()<<endl;
    }
    //cout<<ans;
    return 0;
}