2025-07-27:将数组变相同的最小代价。用go语言，你有两个长度均
2025-07-27：将数组变相同的最小代价。用go语言，你有两个长度均为 n 的整型数组 arr 和 brr，还有一个整数 k。你可以对 arr 进行以下两种操作，次数不限：
1. 将 arr 分成若干连续的子数组，然后按照任意顺序重新排列，这个操作的代价是 k。
2. 选择 arr 中的任意一个元素，并将该元素增加或减少一个正整数 x，代价为 x。
请你计算并返回将 arr 变成 brr 所需的最小总代价。
说明：子数组指数组中一段连续且非空的元素序列。
1 <= arr.length == brr.length <= 100000。
0 <= k <= 2 * 10000000000。
-100000 <= arr[i] <= 100000。
-100000<= brr[i] <= 100000。
输入：arr = [-7,9,5], brr = [7,-2,-5], k = 2。
输出：13。
解释：
将 arr 分割成两个连续子数组：[-7] 和 [9, 5] 然后将它们重新排列成 [9, 5, -7] ，代价为 2 。
将 arr[0] 减小 2 ，数组变为 [7, 5, -7] ，操作代价为 2 。
将 arr[1] 减小 7 ，数组变为 [7, -2, -7] ，操作代价为 7 。
将 arr[2] 增加 2 ，数组变为 [7, -2, -5] ，操作代价为 2 。
将两个数组变相等的总代价为 2 + 2 + 7 + 2 = 13 。
题目来自力扣3424。
大体步骤如下：
1. 计算不进行子数组重排操作时的代价（r1）
o 直接计算将 arr 中每个元素变为对应的 brr 元素所需的操作代价，即对每个 i，计算 |arr[i] - brr[i]|。
o 将所有差的绝对值相加，得到总代价 r1。
o 这里的意思是，没有使用操作1，即没有重排子数组，仅通过增减元素的值来变换。
2. 计算进行一次重排操作后的代价（r2）
o 对两个数组分别进行排序。排序的目的是将两个数组的元素尽量一一对应，减少单元素调整代价。
o 将 arr 和 brr 都排序后，逐一计算排序后数组对应元素的差值的绝对值之和。
o 再加上一次进行子数组重排操作的代价 k。
o 这里的思路是：尽管重排代价较大，但排序后每个元素差距减小，整体调整代价可能更低。
3. 比较两种方案，选取代价最小的
o 比较不重排情况下的代价 r1 和重排一次情况下的代价 r2。
o 返回较小者作为结果，表示最小所需总代价。
核心思路解析（用题目示例解释）
o 原始 arr = [-7, 9, 5]，brr = [7, -2, -5]， k = 2。
o 直接对应调整差价代价大：| -7-7 | + |9+2| + |5+5| = 14 + 11 + 10 = 35 （其实代码算的r1不是35，是更精确的,看上面代码和题目描述，r1 = sum of abs(arr[i] - brr[i])）
o 对两个数组排序后：
- arr排序后: [-7, 5, 9]
- brr排序后: [-5, -2, 7]
o 调整代价为：| -7+5 | + |5+2| + |9-7| = 2 + 7 + 2 = 11 + k = 2，得到13
o 13比不重排调整代价低，最终选择带一次重排的方案。
总结步骤（详细）
1. 直接一步步调整：
o 遍历数组索引 i。
o 计算 arr[i] 调整到 brr[i] 的代价为 abs(arr[i] - brr[i])。
o 累加所有 i 的代价，得到 r1。
2. 尝试子数组重新排列操作：
o 对 arr 进行从小到大排序。
o 对 brr 进行从小到大排序。
o 遍历 i，计算排序后的 arr[i] 调整到 brr[i] 的代价。
o 将所有差值代价相加，再加上子数组重新排列操作代价 k，得到 r2。
3. 取最小代价：
o 比较 r1 和 r2，选择较小值作为最小总代价。
复杂度分析
o 时间复杂度：
- 计算差值代价是 O(n)。
- 对两个数组排序的时间复杂度是 O(n log n)。
- 所以总时间复杂度是 O(n log n)。
o 空间复杂度：
- 排序通常在原数组上进行，不申请额外大数组。
- 代码中只使用了固定的辅助变量。
- 所以空间复杂度为 O(1) 或考虑语言排序算法额外栈空间，最坏也为 O(log n)。
Go完整代码如下：
.
package main
import (
"fmt"
"sort"
)
func minCost(arr []int, brr []int, k int64)int64 {
var r1 int64 = 0
var r2 int64 = k
n := len(arr)
for i := 0; i < n; i++ {
r1 += int64(abs(arr[i] - brr[i]))
}
// 对 arr 和 brr 排序后计算
sort.Ints(arr)
sort.Ints(brr)
for i := 0; i < n; i++ {
r2 += int64(abs(arr[i] - brr[i]))
}
if r1 < r2 {
return r1
}
return r2
}
func abs(x int)int {
if x < 0 {
return -x
}
return x
}
func main() {
arr := []int{-7, 9, 5}
brr := []int{7, -2, -5}
k := int64(2)
result := minCost(arr, brr, k)
fmt.Println(result)
}
Python完整代码如下：
.
# -*-coding:utf-8-*-
def min_cost(arr, brr, k):
r1 = 0
r2 = k
n = len(arr)
for i in range(n):
r1 += abs(arr[i] - brr[i])
arr_sorted = sorted(arr)
brr_sorted = sorted(brr)
for i in range(n):
r2 += abs(arr_sorted[i] - brr_sorted[i])
return min(r1, r2)
if __name__ == "__main__":
arr = [-7, 9, 5]
brr = [7, -2, -5]
k = 2
result = min_cost(arr, brr, k)
print(result)·
我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。
欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展
·