题目描述
思路解析动画文字版
记牢这一句:二分答案 x,判据是把每种商品要的店数 ⌈qi 除以 x⌉ 加起来,累计不超过 n 就可行,收右界去找更小的 x;超了就收左界。下面每一帧都在套它。
摆好数据 · 二分区间 [1, 最大件数]：上面这排是三种商品的件数 15、10、10。右边面板记二分状态。为什么上界取最大件数 15,因为哪怕每店只放到 15 件,每种商品最多也只占一间店,一共才 3 间、不超过 7 间,肯定放得下,所以答案不会比 15 更大。下界取 1,每店至少能放 1 件。答案就落在 1 到 15 之间。
第 1 轮二分 · 取中点 mid = 8：当前二分区间是左界 1、右界 15,取正中间 mid 等于 8。现在假设每间店最多放 8 件,来数一数这样够不够 7 间店装下所有商品。累计门店从 0 开始。
第一种商品 15 件 · 需要 2 间店：紫色指到第一种商品,它有 15 件。每间店至多 8 件,把 15 除以 8 向上取整,得 2 间店。这 2 间店足够装下它的 15 件。累计门店加到 2 间。
第二种商品 10 件 · 需要 2 间店：紫色指到第二种商品,它有 10 件。每间店至多 8 件,把 10 除以 8 向上取整,得 2 间店。这 2 间店足够装下它的 10 件。累计门店加到 4 间。
第三种商品 10 件 · 需要 2 间店：紫色指到第三种商品,它有 10 件。每间店至多 8 件,把 10 除以 8 向上取整,得 2 间店。这 2 间店足够装下它的 10 件。累计门店加到 6 间。
结算 · 累计 6 不超过 7：三种商品要的店数加起来是 6 间。这不超过 7 间,说明每店 8 件是放得下的。既然放得下,就试试更小的上限,把右界收到 mid 等于 8,答案可能还在更左边。新区间是 [1, 8]。
第 2 轮二分 · 取中点 mid = 4：当前二分区间是左界 1、右界 8,取正中间 mid 等于 4。现在假设每间店最多放 4 件,来数一数这样够不够 7 间店装下所有商品。累计门店从 0 开始。
第一种商品 15 件 · 需要 4 间店：紫色指到第一种商品,它有 15 件。每间店至多 4 件,把 15 除以 4 向上取整,得 4 间店。这 4 间店足够装下它的 15 件。累计门店加到 4 间。
第二种商品 10 件 · 需要 3 间店：紫色指到第二种商品,它有 10 件。每间店至多 4 件,把 10 除以 4 向上取整,得 3 间店。这 3 间店足够装下它的 10 件。累计门店加到 7 间。
第三种商品 10 件 · 需要 3 间店：紫色指到第三种商品,它有 10 件。每间店至多 4 件,把 10 除以 4 向上取整,得 3 间店。这 3 间店足够装下它的 10 件。累计门店加到 10 间。
结算 · 累计 10 超过 7：三种商品要的店数加起来是 10 间。这超过了 7 间,说明每店 4 件太挤、放不下。得放宽上限,把左界收到 mid 加 1 等于 5,答案在更右边。新区间是 [5, 8]。
第 3 轮二分 · 取中点 mid = 6：当前二分区间是左界 5、右界 8,取正中间 mid 等于 6。现在假设每间店最多放 6 件,来数一数这样够不够 7 间店装下所有商品。累计门店从 0 开始。
第一种商品 15 件 · 需要 3 间店：紫色指到第一种商品,它有 15 件。每间店至多 6 件,把 15 除以 6 向上取整,得 3 间店。这 3 间店足够装下它的 15 件。累计门店加到 3 间。
第二种商品 10 件 · 需要 2 间店：紫色指到第二种商品,它有 10 件。每间店至多 6 件,把 10 除以 6 向上取整,得 2 间店。这 2 间店足够装下它的 10 件。累计门店加到 5 间。
第三种商品 10 件 · 需要 2 间店：紫色指到第三种商品,它有 10 件。每间店至多 6 件,把 10 除以 6 向上取整,得 2 间店。这 2 间店足够装下它的 10 件。累计门店加到 7 间。
结算 · 累计 7 不超过 7：三种商品要的店数加起来是 7 间。这不超过 7 间,说明每店 6 件是放得下的。既然放得下,就试试更小的上限,把右界收到 mid 等于 6,答案可能还在更左边。新区间是 [5, 6]。
第 4 轮二分 · 取中点 mid = 5：当前二分区间是左界 5、右界 6,取正中间 mid 等于 5。现在假设每间店最多放 5 件,来数一数这样够不够 7 间店装下所有商品。累计门店从 0 开始。
第一种商品 15 件 · 需要 3 间店：紫色指到第一种商品,它有 15 件。每间店至多 5 件,把 15 除以 5 向上取整,得 3 间店。这 3 间店足够装下它的 15 件。累计门店加到 3 间。
第二种商品 10 件 · 需要 2 间店：紫色指到第二种商品,它有 10 件。每间店至多 5 件,把 10 除以 5 向上取整,得 2 间店。这 2 间店足够装下它的 10 件。累计门店加到 5 间。
第三种商品 10 件 · 需要 2 间店：紫色指到第三种商品,它有 10 件。每间店至多 5 件,把 10 除以 5 向上取整,得 2 间店。这 2 间店足够装下它的 10 件。累计门店加到 7 间。
结算 · 累计 7 不超过 7：三种商品要的店数加起来是 7 间。这不超过 7 间,说明每店 5 件是放得下的。既然放得下,就试试更小的上限,把右界收到 mid 等于 5,答案可能还在更左边。新区间是 [5, 5]。
左右界相遇 · 答案 x = 5：二分到左界和右界相遇,都停在 5,区间只剩这一个值,循环结束。这个 5 就是最小的最大值:每间店至多 5 件时,三种商品刚好用 7 间店装下;再小一点就装不下。和开头说的答案对上了。
边界想清:单种商品按 ⌈件数/店数⌉、m 等于 n 时答案是最大件数、只有一间店时全堆一起等于总件数。
面试重点:答案单调所以能二分、判据是每店数向上取整求和比 n、时间 O(m 乘 log C)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def minimizedMaximum(self, n: int, quantities: List[int]) -> int: def check(x): return sum((v + x - 1) // x for v in quantities) <= n return 1 + bisect_left(range(1, 10**6), True, key=check)复杂度
- 时间：O(m·log C)，C 是件数值域(上界)。二分把区间每次减半,做 log C 轮;每一轮的可行性检查要遍历 m 种商品各算一次向上取整,是 O(m)。两者相乘
- 空间：O(1)，只用了 left、right、mid、cnt 这几个变量,不随商品数或件数增长(Python 版的 range 是惰性区间,不真正展开)
易错点
面试追问把动画讲成自己的话
追问这题为什么能二分答案?
追问可行性判据 check(x) 怎么写?
追问复杂度是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
每一个查询的最大美丽值
LeetCode 2070 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题