class Solution {
public:
long long minCost(vector<int>& arr, vector<int>& brr, long long k) {
}
};
3424. 将数组变相同的最小代价
给你两个长度都为 n 的整数数组 arr 和 brr 以及一个整数 k 。你可以对 arr 执行以下操作任意次：
arr 分割成若干个 连续的 子数组，并将这些子数组按任意顺序重新排列。这个操作的代价为 k 。选择 arr 中的任意一个元素，将它增加或者减少一个正整数 x 。这个操作的代价为 x 。
请你返回将 arr 变为 brr 的 最小 总代价。
子数组 是一个数组中一段连续 非空 的元素序列。
示例 1：
输入：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 。
示例 2：
输入：arr = [2,1], brr = [2,1], k = 0
输出：0
解释：
由于数组已经相等，不需要进行任何操作，所以总代价为 0 。
提示：
1 <= arr.length == brr.length <= 1050 <= k <= 2 * 1010-105 <= arr[i] <= 105-105 <= brr[i] <= 105原站题解
java 解法, 执行用时: 21 ms, 内存消耗: 56.1 MB, 提交时间: 2025-01-26 09:28:39
class Solution {
public long minCost(int[] a, int[] b, long k) {
long ans2 = 0;
for (int i = 0; i < a.length; i++) {
ans2 += Math.abs(a[i] - b[i]);
}
if (ans2 <= k) {
return ans2;
}
Arrays.sort(a);
Arrays.sort(b);
long ans1 = k;
for (int i = 0; i < a.length; i++) {
ans1 += Math.abs(a[i] - b[i]);
}
return Math.min(ans1, ans2);
}
}
cpp 解法, 执行用时: 27 ms, 内存消耗: 185 MB, 提交时间: 2025-01-26 09:28:09
class Solution {
public:
long long minCost(vector<int>& a, vector<int>& b, long long k) {
long long ans2 = 0;
for (int i = 0; i < a.size(); i++) {
ans2 += abs(a[i] - b[i]);
}
if (ans2 <= k) {
return ans2;
}
ranges::sort(a);
ranges::sort(b);
long long ans1 = k;
for (int i = 0; i < a.size(); i++) {
ans1 += abs(a[i] - b[i]);
}
return min(ans1, ans2);
}
};
python3 解法, 执行用时: 95 ms, 内存消耗: 32.9 MB, 提交时间: 2025-01-26 09:27:57
class Solution:
def minCost(self, a: List[int], b: List[int], k: int) -> int:
ans2 = sum(abs(x - y) for x, y in zip(a, b))
if ans2 <= k:
return ans2
a.sort()
b.sort()
ans1 = sum(abs(x - y) for x, y in zip(a, b)) + k
return min(ans1, ans2)
golang 解法, 执行用时: 10 ms, 内存消耗: 10.3 MB, 提交时间: 2025-01-26 09:27:29
// 贪心
func minCost(a, b []int, k int64) int64 {
ans2 := int64(0)
for i, x := range a {
ans2 += int64(abs(x - b[i]))
}
if ans2 <= k {
return ans2
}
slices.Sort(a)
slices.Sort(b)
ans1 := k
for i, x := range a {
ans1 += int64(abs(x - b[i]))
}
return min(ans1, ans2)
}
func abs(x int) int { if x < 0 { return -x }; return x }