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 ith 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.

解題思路

Solution

class Solution {
    public long minCost(int[] nums, int[] cost) {
        int left = nums[0];
        int right = nums[0];

        for (int num : nums) {
            left = Math.min(left, num);
            right = Math.max(right, num);
        } // Find the min and max in nums[] array

        long ans = 0;
        while (left < right) {
            int mid = (left + right) / 2;
            long cost1 = helper(nums, cost, mid);
            long cost2 = helper(nums, cost, mid + 1);

            if (cost1 > cost2) {
                left = mid + 1;
                ans = cost2;
            } else {
                right = mid;
                ans = cost1;
            }
        }

        return ans;
    }

    public long helper(int[] nums, int[] cost, int all) {
        long totalCost = 0L;

        for (int i = 0; i < nums.length; i++) {
            totalCost += 1L * Math.abs(nums[i] - all) * cost[i];
        }

        return totalCost;
    }
}