袋子里最少数目的球 图解题解

拆袋子换更小的最大值，这题要返回哪个数

给你一排袋子，nums[i] 是第 i 个袋子的球数，还有上限 maxOperations。一次操作挑一个袋子、把球分成两个正整数堆（比如 5 拆成 1 和 4），最多拆这么多次。开销 = 所有袋子球数的最大值，要让它尽量小并返回。题面 nums=[2,4,8,2]、maxOperations=4 答案是 2：拆满 4 次能把最大值压到 2。

从 1 到最大袋逐个试开销，账算下来多亏

开销最小是 1（每袋只剩 1 个球），最大是 max(nums)（一次都不拆）。笨办法是从 1 到 max(nums) 逐个开销试，每试一个就逐袋算要拆几次、看超不超 maxOperations。可开销是值域（所有可能取值），nums 里的数能到 10⁹，挨个试要扫这么多档、每档还得过一遍 n 个袋子，跑不完。

上限越大越省操作，这条单调让答案可二分

开销 m 定得越大，每个袋子拆到不超过 m 需要的次数越少，总次数跟着往下走；m 越小则越多。开销越大操作只会越少、不回头，于是开销小到某处以下全都拆不完、以上全都够，答案就是第一个够的开销。这条单调分界一立住，就能二分开销逼近它。二分的是开销 m 这个答案值，不是 nums 下标，数组也不用排序。这种猜一个开销再验证行不行的思路，叫二分答案。

判定函数怎么写，(x-1)//m 里那个减 1 从哪来

先把「行不行」做成判定函数 check(m)：逐袋累加分裂次数，总和 ≤ maxOperations 就可行。单袋分裂次数是关键——把 x 个球拆到每袋不超过 m，至少要 ceil(x/m)（向上取整）个袋子；分裂从 1 个整袋起步、每拆一次多一个袋子，凑够就得拆 ceil(x/m)-1 次，减的这个 1 是起步那个整袋。恒等式 ceil(x/m)-1 正好等于 (x-1)//m。二分取中点 mid：可行就 hi 收到 mid（得留住候选），不可行就 lo 跳到 mid+1，撞上就是答案。

nums=[2,4,8,2]、上限 4 走一遍

起点 lo=1、hi=max(nums)=8。第一轮 mid=(1+8)//2=4，(x-1)//4：2→0，4→0，8→(8-1)//4=1，2→0，合计 1 ≤ 4 可行，hi 收到 4。第二轮 lo=1、hi=4，mid=2，(x-1)//2：0、(4-1)//2=1、(8-1)//2=3、0，合计 4 ≤ 4 可行，hi 收到 2。第三轮 lo=1、hi=2，mid=1，(x-1)//1：1、3、7、1，合计 12 > 4 不可行，lo 跳到 2。此时 lo=hi=2，返回 2。

可行时右界收到 mid，减 1 就把答案跳过去

这套 lo<hi、返回 lo 的写法里可行时必须 hi=mid：当前 mid 可能就是最小可行开销，写成 hi=mid-1 会把它甩出区间、返回错的值。另一个坑是把二分架在数组下标上，这题二分的是开销值，认错对象会整个跑偏。复杂度上，开销 1 到 C（C=max(nums)）二分约 log C 轮、每轮 check 扫 n 个袋子，时间 O(n·log C)、空间 O(1)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        def check(mx: int) -> bool:
            return sum((x - 1) // mx for x in nums) <= maxOperations

        return bisect_left(range(1, max(nums) + 1), True, key=check) + 1

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        int l = 1, r = *max_element(nums.begin(), nums.end());
        while (l < r) {
            int mid = (l + r) >> 1;
            long long s = 0;
            for (int x : nums) {
                s += (x - 1) / mid;
            }
            if (s <= maxOperations) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int minimumSize(int[] nums, int maxOperations) {
        int l = 1, r = Arrays.stream(nums).max().getAsInt();
        while (l < r) {
            int mid = (l + r) >> 1;
            long s = 0;
            for (int x : nums) {
                s += (x - 1) / mid;
            }
            if (s <= maxOperations) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}