# 2333. Minimum Sum of Squared Difference
###### tags: `Leetcode` `Medium` `Math` `Greedy` `Priority Queue` `Smear Top Elements`
Link: https://leetcode.com/problems/minimum-sum-of-squared-difference/description/
## 思路
跟[2233. Maximum Product After K Increments](https://hackmd.io/O8P_ou0dTMShNERgRAej_A)类似
先算出所有```Math.abs(nums1[i]-nums2[i])```
由于```k1```, ```k2```即可以+1也可以-1, 所以用在```nums1```和```nums2```上是没差别的
所以直接可以用一个```k=k1+k2```代替
我们要把k用在那些最大的```diff```上
所以我们倒序排列```diff```
对于每一个位置 我们算出 如果前面所有数都减到现在的数一样 需要多少个operation
可以用binary search找到一个位置```p``` 前面所有数都减到和```nums[p]```一样 需要少于等于```k```个operation(如果想减到和```nums[p+1]```一样就需要多于```k```个operation)
所以我们先把这些数减到和```nums[p]```一样
如果对于剩下的```k```，我们算```each = k/p```，```extra = k%p```, 然后我们给前```p```个数每个数再减```each```，再给前```extra```个数减1
注意这里**preSum也需要是long**
## Code

class Solution {
    public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) {
        int n = nums1.length;
        Integer[] diff = new Integer[n];
        for(int i=0; i<n; i++){
            diff[i] = Math.abs(nums1[i]-nums2[i]);
        }
        int k = k1+k2;
        Arrays.sort(diff, Collections.reverseOrder());
        long preSum = 0;
        long[] diff2 = new long[n];
        for(int i=0; i<n; i++){
            preSum += diff[i];
            diff2[i] = (preSum-(long)(diff[i])*(i+1));
        }
        if(preSum<=k) return 0;

        int start = 0, end = n;
        while(start<end){
            int mid = start+(end-start)/2;
            if(diff2[mid]<=(long)k) start = mid+1;
            else end = mid;
        }

        for(int i=0; i<start; i++){
            k -= diff[i]-diff[start-1];
            diff[i] = diff[start-1];
        }

        int each = k/start;
        int extra = k%start;
        for(int i=0; i<start; i++){
            diff[i] -= each;
            if(i<extra) diff[i] -= 1;
        }

        long ans = 0;
        for(int i=0; i<n; i++){
            ans += (long)diff[i]*diff[i];
        }
        return ans;
    }
}