分配给商店的最多商品的最小值 图解题解

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 就方向全反、答案错位。

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;
    }
}