题解:中位数贪心+分类讨论
首先考虑一种特殊情况:数组中所有元素都相等,那么对任何一个元素进行+1或者-1操作都可以,因此对应的代价就是1
如果数组中元素不相等,那么最优解应该是操作完之后,数组中的最大值/最小值与数组中剩下的n-1个数不同,因此直接把数组排序之后,分类讨论,按照中位数贪心求一下这两种情况的答案,最后取一个最小值即可
C++
给定一个长度为 n 的正整数序列 a1,a2,…,an。如果序列中恰好有 n−1 个元素相同,而剩下的一个元素与这些元素不同,则称该序列是“近似一致”的。你可以进行任意次操作,每次操作选择一个元素,将其值加 1 或减 1。请求出将该序列变为近似一致序列所需的最少操作次数。
序列长度 n 满足 1≤n≤105,每个元素 ai 均为正整数且不超过 109。
第一行包含一个整数 n,表示序列的长度。 第二行包含 n 个整数,表示序列的各个元素,整数之间用空格分隔。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.