2448-使数组相等的最小开销

给你两个下标从 0 开始的数组 nums 和 cost ，分别包含 n 个 正 整数。

你可以执行下面操作 任意 次：

• 将 nums 中 任意 元素增加或者减小 1 。

对第 i 个元素执行一次操作的开销是 cost[i] 。

请你返回使 nums 中所有元素 相等 的 最少 总开销。

示例 1：

**输入：** nums = [1,3,5,2], cost = [2,3,1,14]
**输出：** 8
**解释：** 我们可以执行以下操作使所有元素变为 2 ：
- 增加第 0 个元素 1 次，开销为 2 。
- 减小第 1 个元素 1 次，开销为 3 。
- 减小第 2 个元素 3 次，开销为 1 + 1 + 1 = 3 。
总开销为 2 + 3 + 3 = 8 。
这是最小开销。

示例 2：

**输入：** nums = [2,2,2,2,2], cost = [4,2,8,1,3]
**输出：** 0
**解释：** 数组中所有元素已经全部相等，不需要执行额外的操作。

提示：

• n == nums.length == cost.length
• 1 <= n <= 105
• 1 <= nums[i], cost[i] <= 106
• 测试用例确保输出不超过 253-1。

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场周赛的看法~

---

方法一：枚举 + 考察变化量

将 nums 和 cost 绑在一起排序。

首先计算使所有元素都等于 nums}[0] 的总开销 total，以及所有 cost 的和 sumCost。

然后考虑要使所有元素都等于 nums}[1]，total 的变化量是多少：

• 有 cost}[0] 这么多的开销要增加 nums}[1]-\textit{nums}[0]；
• 有 sumCost}-\textit{cost}[0] 这么多的开销要减少 nums}[1]-\textit{nums}[0]。

因此 total 减少了

(\textit{sumCost} - 2 \cdot \textit{cost}[0]) \cdot (\textit{nums}[1]-\textit{nums}[0])

按照这个公式模拟后续 nums}[i]，取所有 total 最小值为答案。

[sol1-Python3]

class Solution:
    def minCost(self, nums: List[int], cost: List[int]) -> int:
        a = sorted(zip(nums, cost))
        ans = total = sum((x - a[0][0]) * c for x, c in a)
        sum_cost = sum(cost)
        for (x0, c), (x1, _) in pairwise(a):
            sum_cost -= c * 2
            total -= sum_cost * (x1 - x0)
            ans = min(ans, total)
        return ans

[sol1-Go]

func minCost(nums, cost []int) int64 {
	type pair struct{ x, c int }
	a := make([]pair, len(nums))
	for i, x := range nums {
		a[i] = pair{x, cost[i]}
	}
	sort.Slice(a, func(i, j int) bool { a, b := a[i], a[j]; return a.x < b.x })

	var total, sumCost int64
	for _, p := range a {
		total += int64(p.c) * int64(p.x-a[0].x)
		sumCost += int64(p.c)
	}
	ans := total
	for i := 1; i < len(a); i++ {
		sumCost -= int64(a[i-1].c * 2)
		total -= sumCost * int64(a[i].x-a[i-1].x)
		ans = min(ans, total)
	}
	return ans
}

func min(a, b int64) int64 { if a > b { return b }; return a }

复杂度分析

• 时间复杂度：O(n\log n)，其中 n 为 nums 的长度。
• 空间复杂度：O(n)。

方法二：中位数贪心

把 cost}[i] 理解成 nums}[i] 的出现次数。

根据中位数贪心，把所有数变成中位数是最优的。

详细证明参考 462. 最小操作次数使数组元素相等 II 。

代码实现时，仍然按照方法一那样排序，然后不断累加 cost}[i]，首次累加到 \ge\dfrac{\textit{sumCost} }{2 时就找到了中位数。

由于 sumCost 可能是奇数，所以要上取整，即首次累加到 \ge\left\lceil\dfrac{\textit{sumCost} }{2}\right\rceil 时就找到了中位数。

[sol2-Python3]

class Solution:
    def minCost(self, nums: List[int], cost: List[int]) -> int:
        a = sorted(zip(nums, cost))
        s, mid = 0, (sum(cost) + 1) // 2
        for x, c in a:
            s += c
            if s >= mid:
                return sum(abs(y - x) * c for y, c in a)  # 把所有数变成 x

[sol2-Go]

func minCost(nums, cost []int) (ans int64) {
	type pair struct{ x, c int }
	a := make([]pair, len(nums))
	sumCost := 0
	for i, c := range cost {
		a[i] = pair{nums[i], c}
		sumCost += c
	}
	sort.Slice(a, func(i, j int) bool { a, b := a[i], a[j]; return a.x < b.x })

	s, mid := 0, (sumCost+1)/2
	for _, p := range a {
		s += p.c
		if s >= mid {
			// 把所有数变成 p.x
			for _, q := range a {
				ans += int64(abs(q.x-p.x)) * int64(q.c)
			}
			break
		}
	}
	return
}

func abs(x int) int { if x < 0 { return -x }; return x }

复杂度分析

• 时间复杂度：O(n\log n)，其中 n 为 nums 的长度。
• 空间复杂度：O(n)。