# 2233. Maximum Product After K Increments
###### tags: `Leetcode` `Medium` `Math` `Greedy` `Priority Queue` `Smear Top Elements`
Link: https://leetcode.com/problems/maximum-product-after-k-increments/description/
## 思路
尽量把k加在比较小的数字上面才能得到optimal结果
### 思路一 Priority Queue $O(klogN)$
### 思路二 Smear Top Elements
我们需要将```K```都分配给较小的元素，尽量“共同富裕”。那么我们将```nums```排序之后，需要将```K```分配给前多少个较小元素呢？显然我们要找到一个位置```p```，使得前```p```个元素之和加上```K```之后再进行平均分配，依然达不到第```p+1```个元素. 为什么呢？如果前```p```个元素进行共产主义之后，均值大于了第```p+1```个元素，那为什么不在前```p+1```个元素内进行“共同富裕”呢，这样就有更多的元素可以趋近一致，从而使乘积更大化。

那么我们如何快速定位这个p呢？我们定义```diff```数组```diff[i] = presum[i]-nums[i]*(i+1)```，表明将前```i+1```个元素都提升至与```nums[i]```相等的话，需要多少“支援”。可以知道，这个```diff```一定是递增的。于是我们可以用二分找到最大的```p```，使得恰好```diff[p]<=K```，意味着K的支援能够将```nums[0:p]```抹平，但是不足以将```nums[0:p+1]```抹平。

我们接下来的任务就是，我们先把```nums[0:p-1]```补到和```nums[0]```一样大 然后看```k```还剩多少 先平均分给```nums[0:p]```每个element ```k/p```这么多 接下来我们给前```k%p```个元素每个都加1即可
## Code
### 思路一 Priority Queue

class Solution {
    public int maximumProduct(int[] nums, int k) {
        Queue<Integer> pq = new PriorityQueue<>();
        int n = nums.length;
        for(int i=0; i<n; i++){
            pq.add(nums[i]);
        }
        for(int i=0; i<k; i++){
            pq.add(pq.poll()+1);
        }
        long ans = 1;
        int mod = 1000000007;
        while(!pq.isEmpty()){
            ans = (ans*pq.poll())%mod;
        }
        return (int)ans;
    }
}

### 思路二 Smear Top Elements

class Solution {
    public int maximumProduct(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        long[] diff = new long[n];
        long presum = 0;
        for(int i=0; i<n; i++){
            presum += nums[i];
            diff[i] = (i+1)*(long)(nums[i])-presum;
        }
        
        int start = 0, end = n;
        while(start<end){
            int mid = start+(end-start)/2;
            if(diff[mid]<=k) start = mid+1;
            else end = mid;
        }

        //set all number before nums[start-1] equals to nums[start-1]
        for(int i=0; i<start; i++){
            k -= nums[start-1]-nums[i];
            nums[i] = nums[start-1];
        }
        //increase nums[0:(start-1)]
        //if k still larger than 0, increase first k%start elements by 1
        int each = k/start;
        int remain = k%start;
        for(int i=0; i<start; i++){
            nums[i] += each;
            if(i<remain) nums[i] += 1;
        }

        long ans = 1;
        int mod = 1000000007;
        for(int i=0; i<n; i++){
            ans = (ans*nums[i])%mod;
        }
        return (int)ans;
    }
}