袋子里最少数目的球

题目

题目来源：力扣（LeetCode）

给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。
你可以进行如下操作至多 maxOperations 次：

选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 正整数 个球。
比方说，一个袋子里有 5 个球，你可以把它们分到两个新袋子里，分别有 1 个和 4 个球，或者分别有 2 个和 3 个球。
你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。

请你返回进行上述操作后的最小开销。

示例 1：

输入：nums = [9], maxOperations = 2
输出：3
解释：
- 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[9] -> [6,3] 。
- 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[6,3] -> [3,3,3] 。
装有最多球的袋子里装有 3 个球，所以开销为 3 并返回 3 。

示例 2：

输入：nums = [2,4,8,2], maxOperations = 4
输出：2
解释：
- 将装有 8 个球的袋子分成装有 4 个和 4 个球的袋子。[2,4,8,2] -> [2,4,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,4,4,4,2] -> [2,2,2,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,4,4,2] -> [2,2,2,2,2,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2] 。
装有最多球的袋子里装有 2 个球，所以开销为 2 并返回 2 。

示例 3：

输入：nums = [7,17], maxOperations = 2
输出：7

思路分析

定义二分搜索的边界
对于一般的二分问题，我们直接定义左右边界如下即可：left = 1, right = 1e9left=1,right=1e9

二分答案的具体过程

确定好了边界后，每次二分搜索时需要判断当前计算值是否满足条件，这里我们引入 check 函数，对当前计算出的开销最大值进行验证。

验证过程也即判断，在maxOperations的操作次数内，能否使所有袋子中的球类数目最大值控制为当前二分计算出的mid。我们只需要遍历一次数组，遇到一个装有小球数量大于mid的袋子，我们便需要将其分成不超过cost的若干份。遍历完整个数组后，我们判断操作次数是否小于等于最大操作次数maxOperations即可。

某一次判断的具体例子

例如，示例 3 中，假设我们当前二分搜索计算出的最大开销为 7，那么在验证过程中，我们遍历整个数组，并期望将全部小球分成若干袋，每袋数量均不超过7 。那么第一个元素 7 自然不需要分解，第二个元素 17 应该被分解到 7 + 7 + 3 的三个袋子中（只需要操作 2 次）。遍历完整个数组后，一共只需要操作 2 次，并未超过最大操作次数。说明当前计算得到的开销可以被满足。由于题目要求我们计算得到最小化开销，所以我们需要继续缩小搜索范围，期望找到更小且满足条件的开销。

var minimumSize = function (nums, maxOperations) {
  let l = 0, r = 0;
  // 计算二分查找上边界r
  for (let n of nums) {
    r = Math.max(n, r);
  }
  // 注意二分边界条件
  while (l + 1 < r) {
    // JS语言特性：注意Math.floor向下取整
    let mid = Math.floor(l + (r - l) / 2), tmp = 0;
    // 遍历数组，遇到一个装有小球数量大于 mid 的袋子，便将其分成不超过 mid 的若干份
    for (let n of nums) {
      tmp += Math.floor((n - 1) / mid);
    }
    // 当前没有用完操作次数，说明还可以进一步降低最终的最小取值，向下调整上边界
    if (tmp <= maxOperations) {
      r = mid;
    }
    // 当前用完了操作次数，说明当前最小取值无法满足条件，向上调整下边界
    else {
      l = mid;
    }
  }
  // 注意最终返回上边界的值
  return r;
};