1760.袋子里最少数目的球

链接：1760.袋子里最少数目的球
难度：Medium
标签：数组、二分查找
简介：给你一个整数数组 nums ，你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。

题解 1 - typescript

• 编辑时间：2021-07-21
• 执行用时：260ms
• 内存消耗：49.4MB
• 编程语言：typescript
• 解法介绍：对最大值进行二分查找。

function minimumSize(nums: number[], maxOperations: number): number {
  return search();
  function search(l = 1, r = Math.max(...nums)): number {
    if (l === r) return l;
    const mid = (l + r) >> 1;
    if (count(mid) <= maxOperations) r = mid;
    else l = mid + 1;
    return search(l, r);
  }
  function count(size: number): number {
    return nums.reduce((total, num) => total + ~~(num / size) + +!!(num % size) - 1, 0);
  }
}

题解 2 - cpp

• 编辑时间：2022-12-20
• 执行用时：164ms
• 内存消耗：54.7MB
• 编程语言：cpp
• 解法介绍：二分查找。

class Solution {
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        int nmin = 1, nmax = 1000000000, nmid;
        while (nmin < nmax) {
            nmid = (nmin + nmax) / 2;
            if (comp(nums, nmid) <= maxOperations) nmax = nmid;
            else nmin = nmid + 1;
        }
        return nmin;
    }
    int comp(vector<int> &nums, int val) {
        int ans = 0;
        for (auto &num : nums) {
            if (num <= val) continue;
            ans += ceil(1.0 * num / val) - 1;
        }
        return ans;
    }
};