塔子哥有一个长度为 n 的数组 a 。但是他觉得一般的数组很不优雅。
对于塔子哥来说,一个长度为 n 的数组,有 n−1 个数相同,有 1 个数与这 n−1 个数不同,则这个数组是优雅的。
题解:中位数贪心+分类讨论
首先考虑一种特殊情况:数组中所有元素都相等,那么对任何一个元素进行+1或者-1操作都可以,因此对应的代价就是1
如果数组中元素不相等,那么最优解应该是操作完之后,数组中的最大值/最小值与数组中剩下的n-1
个数不同,因此直接把数组排序之后,分类讨论,按照中位数贪心求一下这两种情况的答案,最后取一个最小值即可
C++