Problem6373--求中位数

6373: 求中位数

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

中位数,又称中点数,中值。中位数是按顺序排列的一组数据中居于中间位置的数,即在这组数据中,有一半的数据比他大,有一半的数据比他小,这里用 $m_{0.5}$ 来表示中位数。(注意:中位数和众数不同,众数指最多的数,众数有时不止一个,而中位数只能有一个。)
更数学点来描述,有一组数量为 $N$ 的数组:$X_1, X_2, \cdots, X_N$,将它们按从小到大的顺序排序为 $X_{(1)}, X_{(2)}, \cdots, X_{(N)}$。当 $N$ 为奇数的时候, $m_{0.5}=X_{(N+1)/2}$;当 $N$ 为偶数的时候,$m_{0.5}=(X_{(N/2)}+X_{(N/2+1)})/2$。
一个数集中最多有一半的数值小于中位数,也最多有一半的数值大于中位数。如果大于和小于中位数的数值个数均少于一半,那么数集中必有若干值等同于中位数。
现在给你一个长度为 $N$ 的升序数组,请求出该数组的中位数。

Input

一共两行。
第一行包括一个整数 $N\ (1 \leq N \leq 10^6)$。
第二行包括 $N$ 个有序整数,第 $i$ 个整数 $X_i\ (-10^4 \leq X_i \leq 10^4)$ 表示数组对应的数据。

Output

如果 $N$ 为奇数,输出一个整数。
如果 $N$ 为偶数,输出一个保留两位小数点的浮点数。

Sample 1 Input

5
10 20 20 20 30

Sample 1 Output

20
该组数据一共由 $5$ 个数据组成,即 $n$ 为奇数,故按中位数的计算方法,得到中位数为 $20$,即第 $3$ 个数。

Sample 2 Input

8
20 21 23 23 25 29 32 33

Sample 2 Output

24.00
该组数据一共由 $8$ 个数据组成,即 $n$ 为偶数,故按中位数的计算方法,得到中位数 $m_{0.5}=\frac{X_4+X_5}{2}=\frac{23+25}{2}=24.00$,即第四个数和第五个数的平均数。

Source/Category

C++语法 1.5.一维数组