首頁 解題筆記 Leetcode Hard

⭐️⭐️⭐️⭐️⭐️

# 題目敘述

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;
    }
}




單字
** **
!! !!
片語 & 搭配詞
!! !!