2448. Minimum Cost to Make Array Equal

題目描述

You are given two 0-indexed arrays nums and cost consisting each of n positive integers.

You can do the following operation any number of times:

• Increase or decrease any element of the array nums by 1.

The cost of doing one operation on the i^th element is cost[i].

Return the minimum total cost such that all the elements of the array nums become equal.

範例

Example 1:

Input: nums = [1,3,5,2], cost = [2,3,1,14]
Output: 8
Explanation: We can make all the elements equal to 2 in the following way:
- Increase the 0th element one time. The cost is 2.
- Decrease the 1st element one time. The cost is 3.
- Decrease the 2nd element three times. The cost is 1 + 1 + 1 = 3.
The total cost is 2 + 3 + 3 = 8.
It can be shown that we cannot make the array equal with a smaller cost.

Example 2:

Input: nums = [2,2,2,2,2], cost = [4,2,8,1,3]
Output: 0
Explanation: All the elements are already equal, so no operations are needed.

Constraints:

• n == nums.length == cost.length
• 1 <= n <= 10⁵
• 1 <= nums[i], cost[i] <= 10⁶

解答

C++

using LL = long long;

class Solution {
public:
    long long minCost(vector<int>& nums, vector<int>& cost) {
        ios_base::sync_with_stdio(0); cin.tie(0);
        int n = nums.size();
        vector<pair<int, int>> numsWithCost;
        for (int i = 0; i < n; i ++) {
            numsWithCost.push_back({nums[i], cost[i]});
        }
        sort(numsWithCost.begin(), numsWithCost.end(), [](const auto p1, const auto p2) {
            return p1.first < p2.first;
        });

        vector<LL> prefixCost(n, 0);
        prefixCost[0] = numsWithCost[0].second;
        for (int i = 1; i < n; i ++) {
            prefixCost[i] = prefixCost[i - 1] + numsWithCost[i].second;
        }
        LL totalCost = 0;
        for (int i = 1; i < n; i ++) {
            totalCost += (LL)(numsWithCost[i].first - numsWithCost[0].first) * numsWithCost[i].second;
        }
        
        LL ans = totalCost;
        for (int i = 1; i < n; i ++) {
            int numDiff = numsWithCost[i].first - numsWithCost[i - 1].first;
            totalCost += prefixCost[i - 1] * numDiff;
            totalCost -= (prefixCost[n - 1] - prefixCost[i - 1]) * numDiff;
            ans = min(ans, totalCost);
        }
        return ans;
    }
};

Step by Step 的解題思路

Jerry Wu21 June, 2023

Python

class Solution:
    def minCost(self, nums: List[int], cost: List[int]) -> int:
        data = sorted(zip(nums, cost))
        mid = sum(cost) / 2
        spend = 0
        for target, cost in data:
            spend += cost
            if spend >= mid:
                return sum(abs(target - n) * c for n, c in data)

Yen-Chi ChenWed, Jun 21, 2023

Javascript

function minCost(nums, cost) {
  let min = Math.min(...nums);
  let max = Math.max(...nums);
  let result = getCost(min);

  while (max > min) {
    const mid = (max + min) >> 1;
    const left = getCost(mid);
    const right = getCost(mid + 1);
    result = Math.min(left, right);

    if (left < right) {
      max = mid;
    } else {
      min = mid + 1;
    }
  }

  return result;

  function getCost(target) {
    let sum = 0;
    for (let i = 0; i < nums.length; i++) {
      sum += Math.abs(nums[i] - target) * cost[i];
    }

    return sum;
  }
}

本來一看到題目感覺跟2602很像，就嘗試sort + prefix sum再用binary search猜答案，結果一直錯，看答案抄別人的binary search解法。
MarsgoatWed, Jun 21, 2023

Reference

回到題目列表