题解:中位数贪心+分类讨论
首先考虑一种特殊情况:数组中所有元素都相等,那么对任何一个元素进行+1或者-1操作都可以,因此对应的代价就是1
如果数组中元素不相等,那么最优解应该是操作完之后,数组中的最大值/最小值与数组中剩下的n-1
个数不同,因此直接把数组排序之后,分类讨论,按照中位数贪心求一下这两种情况的答案,最后取一个最小值即可
C++
小红有一个长度为 n 的数组 a 。但是他觉得一般的数组很不优雅。
对于小红来说,一个长度为 n 的数组,有 n−1 个数相同,有 1 个数与这 n−1 个数不同,则这个数组是优雅的。
每次操作可以使得数组中一个数的值加 1 或减 1 。
现在,小红想问你,至少要多少次操作,才能使得数组变得优雅。
第一行,一个正整数n(1≤n≤105),表示数组的大小。
第二行,n个正整数ai(1≤ai≤109),表示数组的 n 个元素。
一个整数,表示使得数组变得优雅的最少操作次数。
输入
4
1 2 3 4
输出
2
说明
将 a[0]=1 通过一次加操作修改为 2,将 a[2]=3 通过一次减法操作修改为 2 。
最终 2 次操作数组变为 2 2 2 4
。