题解：中位数贪心+分类讨论

首先考虑一种特殊情况：数组中所有元素都相等，那么对任何一个元素进行+1或者-1操作都可以，因此对应的代价就是1

如果数组中元素不相等，那么最优解应该是操作完之后，数组中的最大值/最小值与数组中剩下的n-1个数不同，因此直接把数组排序之后，分类讨论，按照中位数贪心求一下这两种情况的答案，最后取一个最小值即可

C++

题目内容

小红有一个长度为 $n$ 的数组 $a$ 。但是他觉得一般的数组很不优雅。

对于小红来说，一个长度为 $n$ 的数组，有 $n-1$ 个数相同，有 $1$ 个数与这 $n-1$ 个数不同，则这个数组是优雅的。

每次操作可以使得数组中一个数的值加 $1$ 或减 $1$ 。

现在，小红想问你，至少要多少次操作，才能使得数组变得优雅。

输入描述

第一行，一个正整数$n(1\leq n\leq 10^5)$，表示数组的大小。

第二行，$n$个正整数$a_i(1\leq a_i\leq 10^9)$，表示数组的 $n$ 个元素。

输出描述

一个整数，表示使得数组变得优雅的最少操作次数。

样例

输入

4
1 2 3 4

输出

2

说明

将 $a[0]=1$ 通过一次加操作修改为 $2$，将 $a[2]=3$ 通过一次减法操作修改为 $2$ 。

最终 $2$ 次操作数组变为 2 2 2 4 。