# 2448. Minimum Cost to Make Array Equal
###### tags: `Leetcode` `Hard` `Binary Search`
Link: https://leetcode.com/problems/minimum-cost-to-make-array-equal/description/
## 思路
### Binary Search
思路参考[这里](https://leetcode.com/problems/minimum-cost-to-make-array-equal/solutions/2734162/java-c-python-binary-search/)
convex function的[证明](https://leetcode.com/problems/minimum-cost-to-make-array-equal/solutions/2734728/Pure-math-based-explanation-of-why-Cost-Function-is-convex/)
Assume the final equal value is ```x```
the total cost function ```y = f(x)``` is a convex function
on the range of ```[min(A), max(A)]```.

To find the minimum value of```f(x)```,
we can binary search ```x``` by comparing ```f(mid)``` and ```f(mid + 1)```.
### Weighted Median
思路参考[这里](https://leetcode.com/problems/minimum-cost-to-make-array-equal/solutions/2734183/python3-weighted-median-o-nlogn-with-explanations/)
如果我们要给2减1的cost是2 那其实相当于array里面有两个2 每个2减一的cost是1
这就变成了我们所熟知的问题 给你一大堆数 最少加或减几次1 能使得array里面的所有值相等 答案就是找中位数
因此如果```nums=[1,3,5,2]``` ```cost=[2,3,1,14]```其实相当于计算the minimum total cost such that all the elements of the array ```nums=[1,1,3,3,3,5,2,2,2,2,2,2,2,2,2,2,2,2,2,2]``` become equal, with the cost of doing one operation on each element being 1
类似[0296. Best Meeting Point](https://hackmd.io/iSJUkTnTTKu2AnB8iPowrA)
## Code
Binary Search

class Solution {
    public long minCost(int[] nums, int[] cost) {
        int start = Integer.MAX_VALUE, end = Integer.MIN_VALUE;
        for(int num: nums){
            start = Math.min(start, num);
            end = Math.max(end, num);
        }
        while(start<end){
            int mid = start+(end-start)/2;
            long y1 = findCost(nums, cost, mid);
            long y2 = findCost(nums, cost, mid+1);
            if(y1<y2){
                end = mid;
            }
            else start = mid+1;
        }
        return findCost(nums, cost, start);
    }
    private long findCost(int[] nums, int[] cost, int x){
        int n = nums.length;
        long ans = 0L;
        for(int i=0; i<n; i++){
            ans += (long)cost[i]*Math.abs(nums[i]-x);
        }
        return ans;
    }
}

Weighted Median

class Solution {
    public long minCost(int[] nums, int[] cost) {
        long total = 0;
        for(int i=0; i<nums.length; i++){
            total += cost[i];
        }
        List<int[]> list = new ArrayList<>();
        for(int i=0; i<nums.length; i++){
            list.add(new int[]{nums[i], cost[i]});
        }
        Collections.sort(list, (a,b)->(a[0]-b[0]));
        long curr = 0; 
        int idx = 0, x = -1;
        while(curr<total/2){
            x = list.get(idx)[0];
            curr += list.get(idx++)[1];
        }
        return findCost(nums, cost, x);
    }
    private long findCost(int[] nums, int[] cost, int x){
        int n = nums.length;
        long ans = 0L;
        for(int i=0; i<n; i++){
            ans += (long)cost[i]*Math.abs(nums[i]-x);
        }
        return ans;
    }
}