中位数

中位数

描述

小粽最近学习了中位数的相关知识，她知道了这样一个事实：对于任意 2n−12n-1 个数，将它们从小到大排序后，第 nn 个数就是这个 2n−12n-1 个数的中位数。

现在，小粽想解决这样一个问题：对于一个长度为 2n−12n-1 的数列， 前 2k−1(k=1,2,...,n)2k-1(k=1,2,...,n) 个数的中位数各是多少？

输入

第一行一个正整数 nn，表示有一个长度为 2n−12n-1 的数列。接下来一行 2n−12n-1 个正整数，描述这个数列，用空格隔开。

输

输出 nn 行，第 ii 行表示这个数列的前 2i−12i-1 个数的中位数。

输入样例

输样例

限制

对于 100%100% 的数据，n≤3×105n≤3×105 所有输入数据的数值都在 int 范围内。

提示

[使用两个堆分别保存前一半和后一半大的数。]

代码

#include<iostream> #include<queue> #include <vector>

#include <functional>    // std::greater

#pragma warning(disable:4996)

using namespace std;

/* ===================== 代码实现开始 =================== */

typedef priority_queue<int, vector<int>, less<int>>BigHeap;//有序队列，实际上内部是以堆的方式实现,less表示从大到小排序

typedef priority_queue<int, vector<int>, greater<int>>SmallHeap;

BigHeap bigHeap;//大根堆(即任意节点的值均比其左右叶节点的值大),保存较小一半的数SmallHeap smallHeap;//小根堆(与大根堆相反),保存较大一半的数

//返回值：当前序列中位数的值int getMedian()

{

if (smallHeap.size() >bigHeap.size() && !smallHeap.empty())

return smallHeap.top();

else

return bigHeap.top();

}

//向当前数列末尾插入一个数x void add(int x)

{

if (smallHeap.empty()||x < smallHeap.top())//若x比较大一半的数中的最小值还小，则说明x属于较小一半的数，用大根堆保存

{

bigHeap.emplace(x);

if (bigHeap.size() - smallHeap.size() >= 2)//若两个堆相差为2，则说明需要进行调整，否则例如6 5 4 3 2 1的序列插入后5 4 3 2 1均保存在大根堆中，此时通过return bigHeap.top();获得的数不为中位数

{

smallHeap.emplace(bigHeap.top());

bigHeap.pop();

}

}

else

{

smallHeap.emplace(x);

if (smallHeap.size() - bigHeap.size() >= 2)//若两个堆相差为2，则说明需要进行调整，否则例如6 5 4 3 2 1的序列插入后5 4 3 2 1均保存在大根堆中，此时通过return bigHeap.top();获得的数不为中位数

{

bigHeap.emplace(smallHeap.top());

smallHeap.pop();

}

}

}

/* ==================== 代码实现结束 ================== */

int main()

{

int n;

scanf("%d", &n);

for (int i = 1; i <= 2 * n - 1; i++) {

int a;

scanf("%d", &a);

// fprintf(stderr, "%d\n", a);

add(a);

if (i & 1)

printf("%d\n", getMedian());

}

return 0;

}