Leetcode 3139. Minimum Cost to Equalize Array

• Leetcode 3139. Minimum Cost to Equalize Array
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3139. Minimum Cost to Equalize Array

1. 解题思路

这一题是一道hard的题目，而且看了一下答出率低的离谱，就一开始被吓到了，不过实际做了一下之后，发现用很蠢的方法也一下子过了，就很懵逼……

首先，显然如果cost1的两倍不大于cost2，那么我们显然全部使用操作一加到最大值即可。

然后，我们就是暴力地考察如果最终所有值都变化为$n$的情况即可，且显然有$n\ge max(arr)$。

而关于如何求将数组变为一个具体的n时的情况，此时我们只需要算出所有差值然后进行排序，如果最大值不多于总和的一半，那么我们总可以使用操作二来完成几乎所有的操作，至多只需要执行一次操作一；如果最大值多于综合的一半，那么我们就只能使用操作一来填平其中不够的部分了。

2. 代码实现

给出python代码实现如下：

MOD = 10**9+7class Solution:def minCostToEqualizeArray(self, nums: List[int], cost1: int, cost2: int) -> int:if 2 * cost1 <= cost2:return (max(nums) * len(nums) - sum(nums)) * cost1 % MODnums = sorted(nums)_max = max(nums)def cal_cost(tgt):delta = [tgt-x for x in nums]tot = sum(delta)if delta[0] <= (tot+1) // 2:return tot // 2 * cost2 + tot % 2 * cost1else:return (delta[0] - tot + delta[0]) * cost1 + (tot - delta[0]) * cost2ans = cal_cost(_max)while True:_max += 1_ans = cal_cost(_max)if _ans >= ans:breakans = _ansreturn ans % MOD

提交代码评测得到：耗时1841ms，占用内存31.5MB。