洛谷—— P1168 中位数

https://www.luogu.org/problem/show?pid=1168

题目描述

给出一个长度为N的非负整数序列A[i]，对于所有1 ≤ k ≤ (N + 1) / 2，输出A[1], A[3], …, A[2k - 1]的中位数。[color=red]即[/color]前1，3，5，……个数的中位数。

输入输出格式

输入格式：

输入文件median.in的第1行为一个正整数N，表示了序列长度。

第2行包含N个非负整数A[i] (A[i] ≤ 10^9)。

输出格式：

输出文件median.out包含(N + 1) / 2行，第i行为A[1], A[3], …, A[2i – 1]的中位数。

输入输出样例

输入样例#1：

7
1 3 5 7 9 11 6

输出样例#1：

1
3
5
6

说明

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

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

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

#include <algorithm>
#include <cstdio>
#include <queue>

using namespace std;

priority_queue<int,vector<int>,less<int> >MAX;
priority_queue<int,vector<int>,greater<int> >MIN;
int ans,n,x,a[100000+15];


int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
//    sort(a+1,a+n+1);
    ans=a[1]; printf("%d",ans);
    for(int i=2;i<=n;i+=2)
    {
        if(i+1>n) break;
        for(int j=i;j<=i+1;j++)
            if(a[j]>ans) MIN.push(a[j]);
            else MAX.push(a[j]);
        int size=i>>1;
        if(MIN.size()>size) MAX.push(ans),ans=MIN.top(),MIN.pop();
        if(MAX.size()>size) MIN.push(ans),ans=MAX.top(),MAX.pop();
        printf("
%d",ans);
    }
    return 0;
}