分配给商店的最多商品的最小值 图解题解
这道题到底在问什么
- 输入
- n=7, quantities=[15,10,10]
- 输出
- 5
- 输入
- n=6, quantities=[11,6]
- 输出
- 3
先想最直接的笨办法
三种商品要的店数加起来是 6 间。这不超过 7 间,说明每店 8 件是放得下的。既然放得下,就试试更小的上限,把右界收到 mid 等于 8,答案可能还在更左边。新区间是 [1, 8]。（动画第 9 步）
最优解：一步一步想明白
- 3记牢这一句:二分答案 x,判据是把每种商品要的店数 ⌈qi 除以 x⌉ 加起来,累计不超过 n 就可行,收右界去找更小的 x;超了就收左界。下面每一帧都在套它。
- 4上面这排是三种商品的件数 15、10、10。右边面板记二分状态。为什么上界取最大件数 15,因为哪怕每店只放到 15 件,每种商品最多也只占一间店,一共才 3 间、不超过 7 间,肯定放得下,所以答案不会比 15 更大。下界取 1,每店至少能放 1 件。答案就落在 1 到 15 之间。
- 5当前二分区间是左界 1、右界 15,取正中间 mid 等于 8。现在假设每间店最多放 8 件,来数一数这样够不够 7 间店装下所有商品。累计门店从 0 开始。
- 6紫色指到第一种商品,它有 15 件。每间店至多 8 件,把 15 除以 8 向上取整,得 2 间店。这 2 间店足够装下它的 15 件。累计门店加到 2 间。
- 7紫色指到第二种商品,它有 10 件。每间店至多 8 件,把 10 除以 8 向上取整,得 2 间店。这 2 间店足够装下它的 10 件。累计门店加到 4 间。
- 8紫色指到第三种商品,它有 10 件。每间店至多 8 件,把 10 除以 8 向上取整,得 2 间店。这 2 间店足够装下它的 10 件。累计门店加到 6 间。
- 9三种商品要的店数加起来是 6 间。这不超过 7 间,说明每店 8 件是放得下的。既然放得下,就试试更小的上限,把右界收到 mid 等于 8,答案可能还在更左边。新区间是 [1, 8]。
- 10当前二分区间是左界 1、右界 8,取正中间 mid 等于 4。现在假设每间店最多放 4 件,来数一数这样够不够 7 间店装下所有商品。累计门店从 0 开始。
- 11紫色指到第一种商品,它有 15 件。每间店至多 4 件,把 15 除以 4 向上取整,得 4 间店。这 4 间店足够装下它的 15 件。累计门店加到 4 间。
- 12紫色指到第二种商品,它有 10 件。每间店至多 4 件,把 10 除以 4 向上取整,得 3 间店。这 3 间店足够装下它的 10 件。累计门店加到 7 间。
- 13紫色指到第三种商品,它有 10 件。每间店至多 4 件,把 10 除以 4 向上取整,得 3 间店。这 3 间店足够装下它的 10 件。累计门店加到 10 间。
- 14三种商品要的店数加起来是 10 间。这超过了 7 间,说明每店 4 件太挤、放不下。得放宽上限,把左界收到 mid 加 1 等于 5,答案在更右边。新区间是 [5, 8]。
- 15当前二分区间是左界 5、右界 8,取正中间 mid 等于 6。现在假设每间店最多放 6 件,来数一数这样够不够 7 间店装下所有商品。累计门店从 0 开始。
- 16紫色指到第一种商品,它有 15 件。每间店至多 6 件,把 15 除以 6 向上取整,得 3 间店。这 3 间店足够装下它的 15 件。累计门店加到 3 间。
- 17紫色指到第二种商品,它有 10 件。每间店至多 6 件,把 10 除以 6 向上取整,得 2 间店。这 2 间店足够装下它的 10 件。累计门店加到 5 间。
- 18紫色指到第三种商品,它有 10 件。每间店至多 6 件,把 10 除以 6 向上取整,得 2 间店。这 2 间店足够装下它的 10 件。累计门店加到 7 间。
- 19三种商品要的店数加起来是 7 间。这不超过 7 间,说明每店 6 件是放得下的。既然放得下,就试试更小的上限,把右界收到 mid 等于 6,答案可能还在更左边。新区间是 [5, 6]。
- 20当前二分区间是左界 5、右界 6,取正中间 mid 等于 5。现在假设每间店最多放 5 件,来数一数这样够不够 7 间店装下所有商品。累计门店从 0 开始。
- 21紫色指到第一种商品,它有 15 件。每间店至多 5 件,把 15 除以 5 向上取整,得 3 间店。这 3 间店足够装下它的 15 件。累计门店加到 3 间。
- 22紫色指到第二种商品,它有 10 件。每间店至多 5 件,把 10 除以 5 向上取整,得 2 间店。这 2 间店足够装下它的 10 件。累计门店加到 5 间。
- 23紫色指到第三种商品,它有 10 件。每间店至多 5 件,把 10 除以 5 向上取整,得 2 间店。这 2 间店足够装下它的 10 件。累计门店加到 7 间。
- 24三种商品要的店数加起来是 7 间。这不超过 7 间,说明每店 5 件是放得下的。既然放得下,就试试更小的上限,把右界收到 mid 等于 5,答案可能还在更左边。新区间是 [5, 5]。
- 25二分到左界和右界相遇,都停在 5,区间只剩这一个值,循环结束。这个 5 就是最小的最大值:每间店至多 5 件时,三种商品刚好用 7 间店装下;再小一点就装不下。和开头说的答案对上了。
⚠️ 容易写错的地方
✗ 错：可行性判据方向写反,把累计店数 ≥ n 当可行
✓ 对：累计店数 ≤ n 才可行
每种商品要 ⌈qi/x⌉ 间店,总店数不超过 n 才装得下;写成大于等于会把该收右界的往左收,答案错位
✗ 错：每种商品的店数用普通整除 qi/x
✓ 对：必须向上取整 ⌈qi/x⌉,即 (qi+x-1)/x
整除会丢掉余下的零头件数,少算一间店,把放不下的误判成放得下
✗ 错：二分下界从 0 开始
✓ 对：下界从 1 开始
x 是每店件数上限,取 0 会让 ⌈qi/0⌉ 除以零;每店至少能放 1 件,下界 1 才合法
✗ 错：收右界写成 right = mid - 1
✓ 对：可行时 right = mid,保留 mid 这个候选
mid 本身是一个可行答案,减 1 会把它丢掉;二分找最左可行值时,可行的 mid 要留在区间里
完整代码（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 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)C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#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;
class Solution {
public:
int minimizedMaximum(int n, vector<int>& quantities) {
int left = 1, right = 1e5;
while (left < right) {
int mid = (left + right) >> 1;
int cnt = 0;
for (int& v : quantities) {
cnt += (v + mid - 1) / mid;
}
if (cnt <= n) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
};Java
import java.util.*;
class Solution {
public int minimizedMaximum(int n, int[] quantities) {
int left = 1, right = (int) 1e5;
while (left < right) {
int mid = (left + right) >> 1;
int cnt = 0;
for (int v : quantities) {
cnt += (v + mid - 1) / mid;
}
if (cnt <= n) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}复杂度
时间
O(m·log C)
C 是件数值域(上界)。二分把区间每次减半,做 log C 轮;每一轮的可行性检查要遍历 m 种商品各算一次向上取整,是 O(m)。两者相乘
空间
O(1)
只用了 left、right、mid、cnt 这几个变量,不随商品数或件数增长(Python 版的 range 是惰性区间,不真正展开)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 分配给商店的最多商品的最小值 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题为什么能二分答案?+
因为答案 x 具有单调性:x 越大,每间店能装的越多,越容易在 n 间店内放下;存在一个门槛,门槛及以上的 x 都可行、以下都不可行。求最小可行值,正是二分找最左可行位置的经典场景。
可行性判据 check(x) 怎么写?+
遍历每种商品 qi,算它按每店至多 x 件需要多少间店,也就是 ⌈qi / x⌉,把所有商品的店数加起来。若累计不超过 n,就说明 x 可行,返回真;否则返回假。
复杂度是多少?+
设件数值域为 C,二分做 log C 轮,每一轮的 check 要遍历 m 种商品,是 O(m),所以时间 O(m 乘 log C)。空间只用几个变量,是 O(1)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 分配给商店的最多商品的最小值 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。