class Solution {
public:
long long minCost(vector<int>& nums, vector<int>& cost) {
}
};
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.length1 <= n <= 1051 <= nums[i], cost[i] <= 106原站题解
golang 解法, 执行用时: 84 ms, 内存消耗: 9.7 MB, 提交时间: 2023-09-04 10:12:31
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 }
golang 解法, 执行用时: 52 ms, 内存消耗: 9.8 MB, 提交时间: 2023-09-04 10:12:13
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 }
python3 解法, 执行用时: 76 ms, 内存消耗: 35.1 MB, 提交时间: 2023-09-04 10:11:46
# 中位数贪心
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
python3 解法, 执行用时: 116 ms, 内存消耗: 34.4 MB, 提交时间: 2023-09-04 10:11:17
# 枚举 + 考察变化量
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