题目描述
思路解析
一句话答案：LeetCode 2064 分配给商店的最小最大值：n 家店分 m 种商品、一店只放一种，让件数最多的店尽量轻。上限抬高店只减不增，这条单调让上限可二分，判定按 ⌈件数÷x⌉ 累计店数 ≤n。时间 O(m·log C)、空间 O(1)。
n 间店、m 种商品，这题要把哪个数压到最小
有 n 间零售商店和 m 种商品，第 i 种有 quantities[i] 件。一间店只放一种商品、件数不限；记所有店里商品数目的最大值为 x，要让 x 尽量小。题面 n=7、quantities=[15,10,10] 时答案是 5：每店至多 5 件，三种商品刚好用 7 间店装下，再小一档就塞不进了。
从每店 1 件起一档档试上限，会白试掉一大段
每店上限 x 最小取 1，最大不必超过件数最多的那种商品 15（取到 15，每种商品一间店就装下，才 3 间、没用满 7 间）。笨办法是从 1 起逐个试上限，把各商品店数加起来看超不超 n。可最坏要试到那条分界档才停，次数和上限范围一样多，是 O(m·C)（C 是件数值域），件数一大就试不动了。
每店上限抬高，需要的店只减不增
把每个上限对应的总店数排一排：上限越大，每店装得越多，需要的店数只减不增、越容易塞进 n 间，这就是单调。于是店数够的上限连成一片、不够的连成另一片，答案正是够用那片最左那个——第一个够用的上限，二分就能逼近它。这里二分的是每店上限这个答案、不是商品下标，这类猜答案再验证的解法就叫二分答案。
判定函数怎么数店数，够用和不够又各收哪半
判定函数 check(x) 这样数：某种商品件数、每店至多 x 件，要 ⌈件数 ÷ x⌉ 间店——⌈⌉ 是向上取整，把件数按每堆 x 件分，凑不满一堆的零头也单占一间。各商品店数加起来不超过 n 就够用。二分在 [lo, hi] 取中点 mid：check(mid) 够用就把 hi 收到 mid（可能就是答案，得留）；不够用，lo 跳到 mid+1。缩到 lo、hi 相遇即答案。
拿 n=7、[15,10,10] 一轮轮列出 mid 和店数
起点 lo=1、hi=15。第一轮 mid=(1+15)//2=8，⌈15÷8⌉+⌈10÷8⌉+⌈10÷8⌉=2+2+2=6 ≤ 7 够用，hi 收到 8。第二轮 lo=1、hi=8，mid=4，⌈15÷4⌉+⌈10÷4⌉+⌈10÷4⌉=4+3+3=10 > 7 不够，lo 跳到 5。第三轮 lo=5、hi=8，mid=6，⌈15÷6⌉+⌈10÷6⌉+⌈10÷6⌉=3+2+2=7 ≤ 7 够用，hi 收到 6。第四轮 lo=5、hi=6，mid=5，⌈15÷5⌉+⌈10÷5⌉+⌈10÷5⌉=3+2+2=7 ≤ 7 够用，hi 收到 5。此时 lo=hi=5，循环停，答案 5。
下界搁 0 会当场除零，收右界写 mid−1 会丢答案
二分把上限档数压到约 log C，每档 check 扫 m 种商品，时间 O(m·log C)、空间 O(1)。下界必须从 1 起：写成 0，⌈件数 ÷ 0⌉ 直接除零崩掉，每店本就至少放 1 件。够用时只能写 hi=mid，写成 hi=mid−1 会把可能正是答案的 mid 挤出区间，结果偏大一档。判据也得写累计店数 ≤ n 才够用，写成 ≥ n 就方向全反、答案错位。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这一句:二分答案 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题