解题思路

给定 $n$ 个整数 $a_1,\dots,a_n$ ，希望选一个整数 $x$ 使

\sum_{i=1}^{n} |x-a_i|

最小；若最优解不唯一，取最小的 $x$ 。

P3815.第1题-最稳定稳定剂

1000ms

Difficulty: 2

所属公司 : oppo

算法与标签>排序算法

小O生产了 $n$ 种不同的物质，编号为 $1$ ~ $n$ 。第 $i$ 种物质的活跃值为 $a_i$ 。直接将这些物质融合非常不稳定，因此小O决定额外制作一个稳定剂。

若稳定剂的整数值为 $x$ ，则融合所有物质后产生的不稳定值为 $\sum^n_{i=1}∣x-a_i∣$ 。小O希望找到一个整数 $x$ ，使得不稳定值最小；若存在多个最优的 $x$ ，则选择其中最小的一个。

第一行输入一个整数 $n(1 ≦ n≦2×10^5)$ ，表示不同物质的数量；

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≦ a_i ≦ 10^9)$ ，表示每种物质的活跃值。

输出一个整数，表示你选择的稳定剂数值 $x$ 。

输入

3
1 5 9

输出

说明

对于此样例选择 $5$ 不稳定值为 $|5-1|+|5-5|+|5-9|=8$ ，可以证明此时最小。

输入

4
1 10 2 9

输出

输入

预期输出（选填）