Leetcode 1760

题目要求

给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。

你可以进行如下操作至多 maxOperations 次：

• 选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 正整数 个球。
• 比方说，一个袋子里有 5 个球，你可以把它们分到两个新袋子里，分别有 1 个和 4 个球，或者分别有 2 个和 3 个球。

最小化单个袋子里球数目的 最大值 

核心算法和原理

• 「最小化最大值」，尽量均匀的分配小球

• 换一种思路想：设m为目标，对于给定m，求在maxOperation次分割后能否达到目标

• 设x = nums[i]，每个袋子最后最多装m个球， 则至少需要操作 (⌈x / m⌉ - 1) 次

• 则总的操作需求数为

• cnt(m)单调递减，且值域有限连续，可以考虑二分搜索

• 在[ 1, ranges::max(nums) ]范围内二分搜索m的最大值，使得cnt(m) < maxOperation并尽可能接近maxOperation

• ⌈x/y⌉ = ⌊(x - 1) / y⌋ - 1

代码

class Solution {
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        auto check = [&](int m) -> bool {
            long long cnt = 0;
            for (int x : nums) {
                cnt += (x - 1) / m;
            }
            return cnt <= maxOperations;
        };

        int left = 1, right = ranges::max(nums);
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (check(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};