题解 | #小美的数组操作#

问题分析

• 关键信息： 根据题目要求，我们需要以最少操作次数构造出最多数量的众数。其中「最多数量的众数」是优先的，即优先让数量更多，再考虑最少操作次数；
• 平均值： 题目操作可以分别对两个数加一和减一，最优情况下数组元素和能够被 n 整除时，能够构造最大众数。
• 局部平均： 如果无法构造完全平均，当选择一个数作为工具数，一定可以保证其他 n - 1 个数是平均的。此时，问题的关键在于选择哪些数（哪个数作为工具数）以及选哪个目标平均值。

1   | 123456
4   | 333333
-2  | 444444
...
-32 | 999999

• 中位数： 为了让操作数尽可能小，选择 n - 1 个数的平均值作为目标值是最优的。当不能整除时，要考虑左中位数和右中位数两种情况。
• 贡献度： 数组的最大值和最小值对平均值的贡献度是最大的，相应地也需要更多操作数，所以我们只需要考虑将最大值和最小值作为工具数的情况。

fun main(args: Array<String>) {
    val n = nextInt()
    val nums = nextArrayI(n)
    var fullSum = nums.fold(0L) { it, arr -> it + arr }

    fun count(nums: IntArray, from: Int, to: Int, target: Long): Long {
        var c0 = 0L
        var c1 = 0L
        for (i in from..to) {
            if (nums[i] < target) {
                c0 += target - nums[i]
            } else {
                c1 += nums[i] - target
            }
        }
        return max(c0, c1)
    }

    if (fullSum % n == 0L) {
        // 全局平均
        println(count(nums, 0, n - 1, fullSum / n))
    } else {
        // 局部平均
        nums.sort()
        val target1 = (fullSum - nums[0]) / (n - 1)
        val target2 = (fullSum - nums[n - 1]) / (n - 1)
        val choice1 = min(count(nums, 1, n - 1, target1), count(nums, 1, n - 1, target1 + 1))
        val choice2 = min(count(nums, 0, n - 2, target2), count(nums, 0, n - 2, target2 + 1))
        println(min(choice1, choice2))
    }
    done()
}

也可以提前判断取左中位数还是右中位数：

fun main(args: Array<String>) {
    val n = nextInt()
    val nums = nextArrayI(n)
    var fullSum = nums.fold(0L) { it, arr -> it + arr }
		...
    if (fullSum % n == 0L) {
        // 全局平均
        println(count(nums, 0, n - 1, fullSum / n))
    } else {
        // 局部平均
        nums.sort()
        // 选择 1
        var target1 = (fullSum - nums[0]) / (n - 1)
        if ((fullSum - nums[0]) % (n - 1) > (n - 1) / 2) target1++
        val count1 = count(nums, 1, n - 1, target1)
        // 选择 2
        var target2 = (fullSum - nums[n - 1]) / (n - 1)
        if ((fullSum - nums[n - 1]) % (n - 1) > (n - 1) / 2) target2++
        val count2 = count(nums, 0, n - 2, target2)
        println(min(count1, count2))
    }
    done()
}

复杂度分析：

• 时间复杂度：O(nlgn) 瓶颈在排序；
• 空间复杂度：O(n) nums 数组空间。