Medium

题目描述

给你两个长度为 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：

输入：arr = [2,1], brr = [2,1], k = 0
输出：0
解释：数组已经相等，不需要任何操作，总成本为 0。

约束条件：

  • 1 <= arr.length == brr.length <= 10^5
  • 0 <= k <= 2 * 10^10
  • -10^5 <= arr[i] <= 10^5
  • -10^5 <= brr[i] <= 10^5

解题思路

解题思路

这道题的关键在于理解两种操作的本质：

  1. 重排操作：将数组分割成连续子数组并重新排列，成本为 k
  2. 修改操作：对任意元素加减某个值，成本为修改的绝对值

核心洞察：重排操作实际上可以将数组 arr 重新排列成任意顺序。如果我们使用重排操作，最优策略是将两个数组都排序，然后按位置匹配，这样可以最小化修改成本。

因此，我们需要比较两种策略：

  1. 不使用重排：直接计算 sum(|arr[i] - brr[i]|)
  2. 使用重排：将两数组排序后计算 k + sum(|sorted_arr[i] - sorted_brr[i]|)

通过比较这两种策略的成本，选择较小的即为最优解。

排序后匹配的原理：对于两个已排序的数组，按位置匹配能够最小化总的修改成本，这是一个经典的最优匹配问题。

代码实现

class Solution {
public:
    long long minCost(vector<int>& arr, vector<int>& brr, long long k) {
        int n = arr.size();
        
        // 计算不重排的成本
        long long cost1 = 0;
        for (int i = 0; i < n; i++) {
            cost1 += abs(arr[i] - brr[i]);
        }
        
        // 计算重排后的成本
        vector<int> sortedArr = arr, sortedBrr = brr;
        sort(sortedArr.begin(), sortedArr.end());
        sort(sortedBrr.begin(), sortedBrr.end());
        
        long long cost2 = k;
        for (int i = 0; i < n; i++) {
            cost2 += abs(sortedArr[i] - sortedBrr[i]);
        }
        
        return min(cost1, cost2);
    }
};

class Solution:
    def minCost(self, arr: List[int], brr: List[int], k: int) -> int:
        n = len(arr)
        
        # 计算不重排的成本
        cost1 = sum(abs(arr[i] - brr[i]) for i in range(n))
        
        # 计算重排后的成本
        sorted_arr = sorted(arr)
        sorted_brr = sorted(brr)
        cost2 = k + sum(abs(sorted_arr[i] - sorted_brr[i]) for i in range(n))
        
        return min(cost1, cost2)

public class Solution {
    public long MinCost(int[] arr, int[] brr, long k) {
        int n = arr.Length;
        
        // 计算不重排的成本
        long cost1 = 0;
        for (int i = 0; i < n; i++) {
            cost1 += Math.Abs(arr[i] - brr[i]);
        }
        
        // 计算重排后的成本
        int[] sortedArr = new int[n];
        int[] sortedBrr = new int[n];
        Array.Copy(arr, sortedArr, n);
        Array.Copy(brr, sortedBrr, n);
        Array.Sort(sortedArr);
        Array.Sort(sortedBrr);
        
        long cost2 = k;
        for (int i = 0; i < n; i++) {
            cost2 += Math.Abs(sortedArr[i] - sortedBrr[i]);
        }
        
        return Math.Min(cost1, cost2);
    }
}

var minCost = function(arr, brr, k) {
    const n = arr.length;
    
    // 计算不重排的成本
    let cost1 = 0;
    for (let i = 0; i < n; i++) {
        cost1 += Math.abs(arr[i] - brr[i]);
    }
    
    // 计算重排后的成本
    const sortedArr = [...arr].sort((a, b) => a - b);
    const sortedBrr = [...brr].sort((a, b) => a - b);
    
    let cost2 = k;
    for (let i = 0; i < n; i++) {
        cost2 += Math.abs(sortedArr[i] - sortedBrr[i]);
    }
    
    return Math.min(cost1, cost2);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n log n)主要来自于排序操作
空间复杂度O(n)需要额外空间存储排序后的数组