2967：使数组成为等数数组的最小代价（2116 分）

力扣第 376 场周赛第 3 题

题目

给你一个长度为 n 下标从 0 开始的整数数组 nums 。

你可以对 nums 执行特殊操作 任意次 （也可以 0 次）。每一次特殊操作中，你需要 按顺序 执行以下步骤：

• 从范围 [0, n - 1] 里选择一个下标 i 和一个 正 整数 x 。
• 将 |nums[i] - x| 添加到总代价里。
• 将 nums[i] 变为 x 。

如果一个正整数正着读和反着读都相同，那么我们称这个数是 回文数 。比方说，121 ，2552 和 65756 都是回文数，但是 24 ，46 ，235 都不是回文数。

如果一个数组中的所有元素都等于一个整数 y ，且 y 是一个小于 109 的 回文数 ，那么我们称这个数组是一个 等数数组 。

请你返回一个整数，表示执行任意次特殊操作后使 nums 成为 等数数组 的 最小 总代价。

示例 1：

输入：nums = [1,2,3,4,5]
输出：6
解释：我们可以将数组中所有元素变为回文数 3 得到等数数组，数组变成 [3,3,3,3,3] 需要执行 4 次特殊操作，代价为 |1 - 3| + |2 - 3| + |4 - 3| + |5 - 3| = 6 。
将所有元素变为其他回文数的总代价都大于 6 。

示例 2：

输入：nums = [10,12,13,14,15]
输出：11
解释：我们可以将数组中所有元素变为回文数 11 得到等数数组，数组变成 [11,11,11,11,11] 需要执行 5 次特殊操作，代价为 |10 - 11| + |12 - 11| + |13 - 11| + |14 - 11| + |15 - 11| = 11 。
将所有元素变为其他回文数的总代价都大于 11 。

示例 3 ：

输入：nums = [22,33,22,33,22]
输出：22
解释：我们可以将数组中所有元素变为回文数 22 得到等数数组，数组变为 [22,22,22,22,22] 需要执行 2 次特殊操作，代价为 |33 - 22| + |33 - 22| = 22 。
将所有元素变为其他回文数的总代价都大于 22 。

提示：

• 1 <= n <= 105
• 1 <= nums[i] <= 109

相似问题：

• 0462：最小操作次数使数组元素相等 II
• 2448：使数组相等的最小开销（2005 分）

分析

• 假如不限定回文数，显然找中位数即可
• 限定了回文数，找离中位数最近的回文数并比较即可
• 这即是问题 0564

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()
        mid = str(nums[n//2])
        m = len(mid)
        q,r = divmod(m,2)
        h = int(mid[:q+r])
        b = str(h)+str(h)[-1-r::-1]
        a = str(pow(10,m-1)-1) if h==pow(10,q+r-1) else str(h-1)+str(h-1)[-1-r::-1]
        c = str(pow(10,m)+1) if h==pow(10,q+r)-1 else str(h+1)+str(h+1)[-1-r::-1]
        def cal(x):
            return sum(abs(x-y) for y in nums)
        return min(cal(int(x)) for x in [a,b,c])

71 ms