Minimum Limit of Balls in a Bag

给一个数组, 问如何通过maxOperations个操作, 让数字中最大数字变得最小, 操作是把一个数分割成两个数字的和.

这个题上来肯定用优先队列来一个个找最大的数, 然后分, 但是这里有个问题是, 如何分才能在给出的maxOperations的操作下, 确保最小, 这个策略比较难定. 于是换个思路: 在maxOperations个操作下, 如果结果得到的数字中最大的数字是x, 那么x+1也可以, 所以可以用二分搜索找lower bound.

class Solution {
    public int minimumSize(int[] nums, int maxOperations) { 
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        Arrays.sort(nums); 
        int left = 1;
        int right = nums[nums.length - 1]; 
         while(left < right) {
            int mid = left + (right - left) / 2;
            if(check(nums, mid, maxOperations)) {
                 right = mid;
            }
            else{
                left = mid + 1;
            }
        }
        return left; // never 
    }
    //11       4
    // 4 7     4
    // 4 3 4 4
          
    private boolean check(int[] nums, int m,int max) {
        int count = 0;
        for(int i = nums.length - 1; i >= 0; i--) {
            if(nums[i] <= m)
                break;
            count += (nums[i] - 1) / m;
        }
        return count <= max;
    }
}