README.md

comments	difficulty	edit_url	rating	source	tags
true	困难	https://github.com/doocs/leetcode/edit/main/solution/3100-3199/3139.Minimum%20Cost%20to%20Equalize%20Array/README.md	2666	第 396 场周赛 Q4	贪心 数组 枚举

3139. 使数组中所有元素相等的最小开销

English Version

题目描述

给你一个整数数组 nums 和两个整数 cost1 和 cost2 。你可以执行以下 任一 操作 任意 次：

• 从 nums 中选择下标 i 并且将 nums[i] 增加 1 ，开销为 cost1。
• 选择 nums 中两个 不同 下标 i 和 j ，并且将 nums[i] 和 nums[j] 都 增加 1 ，开销为 cost2 。

你的目标是使数组中所有元素都 相等 ，请你返回需要的 最小开销 之和。

由于答案可能会很大，请你将它对 109 + 7 取余 后返回。

 

示例 1：

输入：nums = [4,1], cost1 = 5, cost2 = 2

输出：15

解释：

执行以下操作可以使数组中所有元素相等：

• 将 nums[1] 增加 1 ，开销为 5 ，nums 变为 [4,2] 。
• 将 nums[1] 增加 1 ，开销为 5 ，nums 变为 [4,3] 。
• 将 nums[1] 增加 1 ，开销为 5 ，nums 变为 [4,4] 。

总开销为 15 。

示例 2：

输入：nums = [2,3,3,3,5], cost1 = 2, cost2 = 1

输出：6

解释：

执行以下操作可以使数组中所有元素相等：

• 将 nums[0] 和 nums[1] 同时增加 1 ，开销为 1 ，nums 变为 [3,4,3,3,5] 。
• 将 nums[0] 和 nums[2] 同时增加 1 ，开销为 1 ，nums 变为 [4,4,4,3,5] 。
• 将 nums[0] 和 nums[3] 同时增加 1 ，开销为 1 ，nums 变为 [5,4,4,4,5] 。
• 将 nums[1] 和 nums[2] 同时增加 1 ，开销为 1 ，nums 变为 [5,5,5,4,5] 。
• 将 nums[3] 增加 1 ，开销为 2 ，nums 变为 [5,5,5,5,5] 。

总开销为 6 。

示例 3：

输入：nums = [3,5,3], cost1 = 1, cost2 = 3

输出：4

解释：

执行以下操作可以使数组中所有元素相等：

• 将 nums[0] 增加 1 ，开销为 1 ，nums 变为 [4,5,3] 。
• 将 nums[0] 增加 1 ，开销为 1 ，nums 变为 [5,5,3] 。
• 将 nums[2] 增加 1 ，开销为 1 ，nums 变为 [5,5,4] 。
• 将 nums[2] 增加 1 ，开销为 1 ，nums 变为 [5,5,5] 。

总开销为 4 。

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 106
• 1 <= cost1 <= 106
• 1 <= cost2 <= 106

解法

方法一

Python3

Java

C++

Go