袋子里最少数目的球 图解题解
这道题到底在问什么
- 输入
- nums=[9], ops=2
- 输出
- 3
- 输入
- nums=[9], ops=1
- 输出
- 5
- 输入
- nums=[2,4,8,2], ops=4
- 输出
- 2
最优解：一步一步想明白
- 3记牢:开销 m 越大越好办,可行性单调,于是在 1 到 max(nums) 上二分 m。检查一个 m:每个袋子分裂 (x-1)//m 次,求和 ≤ maxOperations 则可行、收紧右界,否则抬高左界。二分的是开销值,不是下标。
- 4先看清画面。上面这排格子是 4 个袋子 2,4,8,2,开销就是里面最大的那个,现在是 8。我们最多拆 4 次,想把这个最大值压到尽量小。右边面板记三件事:开销的候选范围、当前正在检验的开销 m、已经用掉的分裂次数,现在都还没开始。思路不是硬拆,而是二分猜一个开销 m,再验证它办不办得到。
- 5先框定答案的范围。开销最小能到 1,每袋只放 1 个球;最大不用超过 8,因为一次都不拆时最大袋就是 8。所以答案一定落在 1 到 8 这个闭区间里。接下来我们不逐个试,而是二分:取中点当候选开销 m,验证「能不能让每个袋子都不超过 m」。请记住,右边面板里动的是开销 m 的范围,不是数组下标,数组这排袋子始终不动。
- 6开始第一轮二分。当前范围是 1 到 8,取中点,m 等于 1 加 8 整除 2 得 4。也就是先问:能不能拆到每个袋子都不超过 4 个球?下面逐个袋子算它要分裂几次,把次数累加起来,再和上限 4 比。
- 7看第 0 个袋子,里面有 2 个球,要拆到每袋不超过 4。至少需要 2 除以 4 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 2 减 1 再整除 4,算出来是 0 次。这个袋子本来就不超过 4,一次都不用拆。
- 8看第 1 个袋子,里面有 4 个球,要拆到每袋不超过 4。至少需要 4 除以 4 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 4 减 1 再整除 4,算出来是 0 次。这个袋子本来就不超过 4,一次都不用拆。
- 9看第 2 个袋子,里面有 8 个球,要拆到每袋不超过 4。至少需要 8 除以 4 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 8 减 1 再整除 4,算出来是 1 次。把它累加进已用分裂,现在合计 1 次。
- 10看第 3 个袋子,里面有 2 个球,要拆到每袋不超过 4。至少需要 2 除以 4 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 2 减 1 再整除 4,算出来是 0 次。这个袋子本来就不超过 4,一次都不用拆。
- 11四个袋子算完,分裂合计 1 次,不超过上限 4,说明开销压到 4 是办得到的。既然能到 4,那更大的开销就不用看了,把右界收到 4,范围变成 1 到 4。注意 4 本身可能就是答案,所以右界取 4 而不是 4 减 1,继续往更小里试。
- 12第二轮二分。上一轮把范围收到了 [1, 4],取中点得到候选开销 m 等于 2。同样地,问一句:能不能让每个袋子都不超过 2 个球?逐袋算分裂次数、累加、再和上限 4 比。
- 13看第 0 个袋子,里面有 2 个球,要拆到每袋不超过 2。至少需要 2 除以 2 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 2 减 1 再整除 2,算出来是 0 次。这个袋子本来就不超过 2,一次都不用拆。
- 14看第 1 个袋子,里面有 4 个球,要拆到每袋不超过 2。至少需要 4 除以 2 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 4 减 1 再整除 2,算出来是 1 次。把它累加进已用分裂,现在合计 1 次。
- 15看第 2 个袋子,里面有 8 个球,要拆到每袋不超过 2。至少需要 8 除以 2 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 8 减 1 再整除 2,算出来是 3 次。把它累加进已用分裂,现在合计 4 次。
- 16看第 3 个袋子,里面有 2 个球,要拆到每袋不超过 2。至少需要 2 除以 2 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 2 减 1 再整除 2,算出来是 0 次。这个袋子本来就不超过 2,一次都不用拆。
- 17四个袋子算完,分裂合计 4 次,不超过上限 4,说明开销压到 2 是办得到的。既然能到 2,那更大的开销就不用看了,把右界收到 2,范围变成 1 到 2。注意 2 本身可能就是答案,所以右界取 2 而不是 2 减 1,继续往更小里试。
- 18第三轮二分。上一轮把范围收到了 [1, 2],取中点得到候选开销 m 等于 1。同样地,问一句:能不能让每个袋子都不超过 1 个球?逐袋算分裂次数、累加、再和上限 4 比。
- 19看第 0 个袋子,里面有 2 个球,要拆到每袋不超过 1。至少需要 2 除以 1 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 2 减 1 再整除 1,算出来是 1 次。把它累加进已用分裂,现在合计 1 次。
- 20看第 1 个袋子,里面有 4 个球,要拆到每袋不超过 1。至少需要 4 除以 1 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 4 减 1 再整除 1,算出来是 3 次。把它累加进已用分裂,现在合计 4 次。
- 21看第 2 个袋子,里面有 8 个球,要拆到每袋不超过 1。至少需要 8 除以 1 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 8 减 1 再整除 1,算出来是 7 次。把它累加进已用分裂,现在合计 11 次。
- 22看第 3 个袋子,里面有 2 个球,要拆到每袋不超过 1。至少需要 2 除以 1 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 2 减 1 再整除 1,算出来是 1 次。把它累加进已用分裂,现在合计 12 次。
- 23四个袋子算完,分裂合计 12 次,超过了上限 4,说明开销压到 1 太狠、拆不过来。那 1 以及更小的都不行,把左界抬到 2,范围变成 2 到 2。左右界撞到一起了,二分到此收束。
- 24二分收束了。左界和右界都停在 2,说明 2 是能办到的最小开销:它可行,而比它小的 1 已经验证过办不到。把开销压到 2 的具体拆法是,那个 8 拆成 4 和 4、再各自拆成两个 2,4 也拆成两个 2,恰好用满 4 次分裂,最后全场每袋都不超过 2。
- 25收个尾。整道题的巧劲在于把「怎么拆」这个难题,翻译成「开销能不能压到 m」这个好答的判断题,再靠单调性二分开销。nums = 2,4,8,2、maxOperations = 4,我们只检验了 4、2、1 三个候选开销,就锁定最小开销是 2。二分让候选个数从线性变成对数级,可行性检查每次线性扫一遍袋子,又快又稳。
⚠️ 容易写错的地方
✗ 错：把二分用在数组下标上,以为是在 nums 里找位置
✓ 对：二分的是「开销 m 这个答案值」,范围是 1 到 max(nums),不是数组下标
这是二分答案最核心的转弯。答案的取值有单调可行性,才把二分从「找元素」升级成「找答案分界点」。误当成下标二分会完全跑偏,数组也不需要排序
✗ 错：分裂次数公式记错,写成 x//m 或 ceil(x/m)
✓ 对：单袋分裂次数 = ceil(x/m) - 1 = (x-1)//m
拆到每袋不超过 m 至少要 ceil(x/m) 个袋子,而从 1 个袋子变成这么多个,分裂次数是袋子数减 1。少减 1 会把可行的 m 误判成不可行,多减会漏拆。x 减 1 再整除 m 正好等于 ceil(x/m) 减 1,记这个更稳
✗ 错：脱离模板笼统说「hi = mid 减 1 是错的」
✓ 对：本稿是 lo 小于 hi、最后返回 lo 的 lower_bound 写法,可行时必须 hi = mid 保留候选;不可行时 lo = mid + 1
在这套 lo 小于 hi、返回 lo 的写法里,当前 mid 可行就得写 hi = mid 把这个候选留下;误写成 hi = mid 减 1 会破坏二分不变量,可能把真正的答案本身跳过去,得到一个错误的值(不是简单地偏大)。要说明的是,hi = mid 减 1 本身并不错,它属于 lo 小于等于 hi 那套模板,脱离模板断言它错反而会误导
完整代码（Python / C++ / Java）
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) + 1C++
#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;
}
}复杂度
时间
O(n log C)
n 是袋子个数,C 是最大的袋子球数 max(nums)。二分在开销范围 1 到 C 上进行,最多 log C 轮;每一轮做一次可行性检查,要扫一遍全部 n 个袋子累加分裂次数,是 O(n)。两者相乘就是 O(n log C)。演示里 n 等于 4、C 等于 8,只检验了 3 个候选开销就收敛
空间
O(1)
按峰值算。除了输入数组,只用了 lo、hi、mid 和一个累加分裂次数的变量,都是常数个标量,不随规模增长。Python 里的 range 是惰性对象、不真的展开成数组,bisect 也只用常数额外空间。全程没有开新数组,所以额外空间是常数 O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 袋子里最少数目的球 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么开销可以拿来二分?单调性到底体现在哪?+
关键是「给定开销 m 能不能办到」这个判断关于 m 是单调的。m 定得越大,每个袋子拆到每袋不超过 m 需要的分裂次数越少,总分裂次数只减不增;m 越小则越多。于是存在一条分界线,m 大于等于它就可行、小于它就不可行,不会出现可行和不可行来回横跳。有了这个单调性,就能像在有序序列里找边界一样二分这个 m,每次用可行性检查判断往左收还是往右收,把线性枚举压成对数级。
单个袋子的分裂次数为什么正好是 (x-1)//m?+
把 x 个球拆成每袋不超过 m 个,至少需要 x 除以 m 向上取整个袋子,记作 ceil(x/m)。而分裂是从一个袋子开始,每分裂一次多出一个袋子,要得到 ceil(x/m) 个袋子就得分裂 ceil(x/m) 减 1 次。再用一个取整恒等式,ceil(x/m) 减 1 恰好等于 x 减 1 再整除 m,所以直接写 (x-1)//m 又简洁又不会碰到向上取整的边界坑,比如 x 正好被 m 整除时两种写法也一致。
和普通的「在有序数组里二分找目标」比,这题难在哪?+
普通二分的判定是「当前值和目标比大小」,一眼就能写;二分答案的难点在于要自己设计判定函数,把「答案是否可行」翻译成一段可计算的检查。这题的判定就是那句可行性检查:逐袋累加 (x-1)//m 再和 maxOperations 比。想清楚判定单调、范围取 1 到 max(nums)、以及可行时右界取 mid 这三点,剩下的二分骨架就和普通二分一模一样了。这类题的通用套路是,先问「能不能达到 m」比直接求最优值好答得多。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 袋子里最少数目的球 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。