[2448. Minimum Cost to Make Array Equal](https://leetcode.com/problems/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^5^
* 1 <= `nums[i]`, `cost[i]` <= 10^6^

### 解答
#### 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 的解題思路](https://docs.google.com/presentation/d/1HOILkYg8cTbfNPoczOv8fpwnErCnACURp4itfmSKPJc/edit?usp=sharing)

> [name=Jerry Wu][time=21 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)

> [name=Yen-Chi Chen][time=Wed, 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解法。
> [name=Marsgoat][time=Wed, Jun 21, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)