题解:
二分
1.题目可以转换为:操作 maxOperations 次,每个袋子的最大值小于等于 ans,求这个ans的最小值
2.可以从[1, nums数组的最大值]这个区间开始二分
3.判断函数:
- nums[i] <= ans opt = 0
- nums[i] > ans opt = (nums[i] - 1) / ans
class Solution {
public int minimumSize(int[] nums, int maxOperations) {
int left = 1;
int right = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
right = Math.max(right, nums[i]);
}
while (left < right) {
int mid = (left + right ) / 2 ;
if (check(mid,nums,maxOperations)) left = mid + 1;
else right = mid;
}
return left;
}
private boolean check(int mid, int[] nums, int maxOperations) {
int opt = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > mid) {
opt += (nums[i] - 1) / mid;
}
}
return opt > maxOperations;
}
}
标签:少数,right,nums,int,mid,maxOperations,袋子,1760,left
From: https://www.cnblogs.com/eiffelzero/p/16993850.html