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;
}
}