D.二分查找－二分答案－最小化最大值——1760. 袋子里最少数目的球

题目链接：1760. 袋子里最少数目的球（中等）

算法原理：

解法：二分查找

25ms击败94.70%

时间复杂度O(Nlogn)

①目标变量：开销

②目标条件：经过最多maxOperations次操作使得袋子开销最小

③转换逻辑：经过最多maxOperations次操作后，能否让所有袋子的球都≤mid

具体步骤：

①确定边界：

left：1，题目保证了至少有1个球，因此至少需要1个开销

right：数组中的最大值，不经过任何操作时，数组中最大值作为开销能够装下任一袋子的球

②确定二分模型：

开销 ↑ 操作次数 ↓ 呈负相关单调，由于要让开销尽量小，因此采用最左端点模型

③check方法设计：判断经过最多maxOperations次操作后，能否让所有袋子的球都≤mid，只需要知道每个袋子中的球要经过多少次操作能让球数≤mid，那么对应操作次数r=x/mid，由于当求数为mid时无需再进行操作了，因此我们需要向下取整，最终式子为r=(x-1)/mid，在累计操作次数时，如果发现已经超过了最大操作次数了，那么肯定无法让所有袋子的球都≤mid，直接返回false，否则就在最后判断，根据r≤m进行返回

Java代码：

class Solution { public int minimumSize(int[] nums, int m) { int left=1,right=0; for(int x:nums) right=Math.max(right,x); while(left<right){ int mid=left+(right-left)/2; if(!check(mid,nums,m)) left=mid+1; else right=mid; } return left; } //判断经过最多maxOperations次操作后，能否让所有袋子的球都≤mid private boolean check(int mid,int[] nums,int m){ long r=0;//累计操作次数 for(int x:nums){ //对每个袋子x，计算需要的操作次数累加 r+=(x-1)/mid; //次数超过m，直接返回false if(r>m) return false; } //总操作次数≤m，说明mid可行 return r<=m; } }