问题2662--小H的面试难题

2662: 小H的面试难题

时间限制: 1 Sec  内存限制: 128 MB
提交: 385  解决: 110
[状态] [讨论版] [提交] [命题人:]
题目描述

H前段时间在面试,面试官问了一个中位数的问题:一个长度为n的序列A, 怎么求A所有前缀子串的中位数。小H当时想破头也没想到,所以今天不得不向你求助。可是前缀子串有时候太多了,因此,小H好心帮你减轻工作量,你只用求长度为奇数的前缀子串的中位数。

输入

第一行为n,表示序列长度;随后的n个自然数。

(1e3<=n<=1e5, 1<=a[i]<=1e9)

输出

输出(n + 1/2个数,分别是子串[0,0],[0,2],[0,4].....的中位数。

样例输入 Copy
12
16 23 28 19 9 24 27 10 22 6 15 1
样例输出 Copy
16
23
19
23
22
19
来源/分类