Leetcode 2448. Minimum Cost to Make Array Equal

[Woodyiiiiiii]

这道题一看就要用二分法，否则超时。

关键在于，往左往右的条件是什么？向哪边cost大呢？

一直没想到，其实题解在于，cost是一个凸函数，论证可以找下。但不妨这么想，以后实在想不到条件的，可以赌一把是不是凹函数还是凸函数。

class Solution {
    public long minCost(int[] nums, int[] cost) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        int costMaxI = 0, costMax = 0;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }

        long minSum = Long.MAX_VALUE;
        while (min <= max) {
            int mid = min + (max - min) / 2;
            long sum = getSum(nums, mid, cost);
            minSum = Math.min(minSum, sum);
            int midR = mid + 1;
            if (midR > max) {
                max = mid - 1;
            } else {
                long sumR = getSum(nums, midR, cost);
                if (sumR < sum) {
                    min = mid + 1;
                } else {
                    max = mid - 1;
                }
            }
        }

        return minSum;
    }
    
    private long getSum(int[] nums, int mid, int[] cost) {
        long sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += (long) Math.abs(nums[i] - mid) * cost[i];
        }
        return sum;
    }
}

---

• https://leetcode.com/problems/minimum-cost-to-make-array-equal/