Hard
题目描述
给你一个整数数组 nums 和两个整数 cost1 和 cost2。你可以执行以下操作任意次数：
- 选择数组
nums中的一个下标i，将nums[i]增加 1，开销为cost1。 - 选择数组
nums中两个不同的下标i和j，将nums[i]和nums[j]都增加 1，开销为cost2。
返回使数组中所有元素相等所需的最小开销。
由于答案可能很大，请返回答案对 10^9 + 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
示例 3：
输入：nums = [3,5,3], cost1 = 1, cost2 = 3
输出：4
约束条件：
1 <= nums.length <= 10^51 <= nums[i] <= 10^61 <= cost1 <= 10^61 <= cost2 <= 10^6
解题思路
这道题的关键在于确定最终的目标值和选择最优的操作策略。
核心思路分析：
目标值选择：所有元素最终都要变成某个值
target，显然target不会小于原数组的最大值。我们需要枚举可能的目标值。操作策略：
- 如果
cost2 >= 2 * cost1，那么使用两次操作1总是比使用一次操作2更便宜，所以只用操作1 - 否则，我们应该尽可能多地使用操作2（同时增加两个元素）
- 如果
贪心策略：当
cost2 < 2 * cost1时，我们优先配对较小的元素使用操作2。但需要特别处理最小元素，因为它可能需要增加很多，导致无法完全配对。目标值枚举：我们需要枚举从
max(nums)开始的若干个可能的目标值。关键观察是，当目标值足够大时，所有增量都可以通过操作2完成（除了可能剩余的一个），此时成本变化趋于线性。
算法流程：
- 如果
cost2 >= 2 * cost1，直接用操作1，成本为sum(target - nums[i]) * cost1 - 否则，对于每个可能的目标值，计算使用操作2的最优分配，找出最小成本
代码实现
class Solution {
public:
int minCostToEqualizeArray(vector<int>& nums, int cost1, int cost2) {
const int MOD = 1e9 + 7;
int n = nums.size();
if (n == 1) return 0;
int maxVal = *max_element(nums.begin(), nums.end());
long long totalDiff = 0;
for (int num : nums) {
totalDiff += maxVal - num;
}
// 如果cost2太大，直接用cost1
if (cost2 >= 2LL * cost1) {
return (totalDiff * cost1) % MOD;
}
long long minCost = LLONG_MAX;
// 枚举目标值
for (int target = maxVal; target <= maxVal + n; target++) {
long long total = 0, maxDiff = 0;
for (int num : nums) {
long long diff = target - num;
total += diff;
maxDiff = max(maxDiff, diff);
}
long long cost;
if (maxDiff * 2 <= total) {
// 可以完全配对
cost = (total / 2) * cost2 + (total % 2) * cost1;
} else {
// 最大差值太大，需要单独处理
long long pairs = total - maxDiff;
long long singles = maxDiff - pairs;
cost = pairs * cost2 + singles * cost1;
}
minCost = min(minCost, cost);
}
return minCost % MOD;
}
};
class Solution:
def minCostToEqualizeArray(self, nums: List[int], cost1: int, cost2: int) -> int:
MOD = 10**9 + 7
n = len(nums)
if n == 1:
return 0
max_val = max(nums)
total_diff = sum(max_val - num for num in nums)
# 如果cost2太大，直接用cost1
if cost2 >= 2 * cost1:
return (total_diff * cost1) % MOD
min_cost = float('inf')
# 枚举目标值
for target in range(max_val, max_val + n + 1):
total = 0
max_diff = 0
for num in nums:
diff = target - num
total += diff
max_diff = max(max_diff, diff)
if max_diff * 2 <= total:
# 可以完全配对
cost = (total // 2) * cost2 + (total % 2) * cost1
else:
# 最大差值太大，需要单独处理
pairs = total - max_diff
singles = max_diff - pairs
cost = pairs * cost2 + singles * cost1
min_cost = min(min_cost, cost)
return min_cost % MOD
public class Solution {
public int MinCostToEqualizeArray(int[] nums, int cost1, int cost2) {
const int MOD = 1000000007;
int n = nums.Length;
if (n == 1) return 0;
int maxVal = nums.Max();
long totalDiff = nums.Sum(num => (long)(maxVal - num));
// 如果cost2太大，直接用cost1
if (cost2 >= 2L * cost1) {
return (int)((totalDiff * cost1) % MOD);
}
long minCost = long.MaxValue;
// 枚举目标值
for (int target = maxVal; target <= maxVal + n; target++) {
long total = 0, maxDiff = 0;
foreach (int num in nums) {
long diff = target - num;
total += diff;
maxDiff = Math.Max(maxDiff, diff);
}
long cost;
if (maxDiff * 2 <= total) {
// 可以完全配对
cost = (total / 2) * cost2 + (total % 2) * cost1;
} else {
// 最大差值太大，需要单独处理
long pairs = total - maxDiff;
long singles = maxDiff - pairs;
cost = pairs * cost2 + singles * cost1;
}
minCost = Math.Min(minCost, cost);
}
return (int)(minCost % MOD);
}
}
var minCostToEqualizeArray = function(nums, cost1, cost2) {
const MOD = 1000000007;
const n = nums.length;
const max = Math.max(...nums);
const min = Math.min(...nums);
if (n === 1) return 0;
let minCost = Infinity;
// Try different target values
for (let target = max; target <= max + n; target++) {
let totalNeeded = 0;
let maxNeeded = 0;
for (let num of nums) {
const needed = Math.max(0, target - num);
totalNeeded += needed;
maxNeeded = Math.max(maxNeeded, needed);
}
if (totalNeeded === 0) {
minCost = 0;
break;
}
let cost = Infinity;
// Case 1: Use only operation 1
cost = Math.min(cost, (totalNeeded % MOD) * cost1);
// Case 2: Use operation 2 as much as possible
if (cost2 < 2 * cost1) {
const otherNeeded = totalNeeded - maxNeeded;
if (maxNeeded <= otherNeeded) {
// Can pair everything
const pairs = Math.floor(totalNeeded / 2);
const remaining = totalNeeded % 2;
cost = Math.min(cost, pairs * cost2 + remaining * cost1);
} else {
// maxNeeded > otherNeeded
const excess = maxNeeded - otherNeeded;
// Use operation 2 for otherNeeded pairs, operation 1 for excess
cost = Math.min(cost, otherNeeded * cost2 + excess * cost1);
// Alternative: balance by using more operation 1 on others
if (excess % 2 === 0) {
const extraOp1 = excess;
const newMaxNeeded = maxNeeded;
const newOtherNeeded = otherNeeded + extraOp1;
const newTotal = newMaxNeeded + newOtherNeeded;
const pairs = Math.floor(newTotal / 2);
const remaining = newTotal % 2;
cost = Math.min(cost, pairs * cost2 + remaining * cost1 + extraOp1 * cost1);
} else {
const extraOp1 = excess + 1;
const newMaxNeeded = maxNeeded;
const newOtherNeeded = otherNeeded + extraOp1;
const newTotal = newMaxNeeded + newOtherNeeded;
const pairs = Math.floor(newTotal / 2);
const remaining = newTotal % 2;
cost = Math.min(cost, pairs * cost2 + remaining * cost1 + extraOp1 * cost1);
}
}
}
minCost = Math.min(minCost, cost);
}
return minCost % MOD;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n²) - 枚举O(n)个目标值，每次计算需要O(n)时间 |
| 空间复杂度 | O(1) - 只使用常数额外空间 |