前言

以前也做多好几题，最大值中最小值的题目，印象之中都是用二分来解决。
今天就总结一下这个场景。
主要是，题目让你找一个值，你发现这个值具有二段性和单调性就可以用二分来解决。

题目

leetcode 266周赛 第三题
链接：https://leetcode-cn.com/problems/minimized-maximum-of-products-distributed-to-any-store/

题目描述

给你一个整数 n ，表示有 n 间零售商店。总共有 m 种产品，每种产品的数目用一个下标从 0 开始的整数数组 quantities 表示，其中 quantities[i] 表示第 i 种商品的数目。

你需要将 所有商品 分配到零售商店，并遵守这些规则：

一间商店 至多 只能有 一种商品 ，但一间商店拥有的商品数目可以为 任意 件。
分配后，每间商店都会被分配一定数目的商品（可能为 0 件）。用 x 表示所有商店中分配商品数目的最大值，你希望 x 越小越好。也就是说，你想 最小化 分配给任意商店商品数目的 最大值 。
请你返回最小的可能的 x 。
----------------------------------------------
示例 1：
输入：n = 6, quantities = [11,6]
输出：3
解释： 一种最优方案为：
- 11 件种类为 0 的商品被分配到前 4 间商店，分配数目分别为：2，3，3，3 。
- 6 件种类为 1 的商品被分配到另外 2 间商店，分配数目分别为：3，3 。
分配给所有商店的最大商品数目为 max(2, 3, 3, 3, 3, 3) = 3 。

----------------------------------------------
数据规模
m == quantities.length
1 <= m <= n <= 105
1 <= quantities[i] <= 105

思路

如果做得少，真得不会想到会用二分。这题首先可以用数据规模来推测一定是O（nlogn）的算法。
题目的答案是一个最大值中的最小值。
这个值越大，就越容易符合题目要求； 加入5是一个可行解，那么6 之后的答案，必然也是可行解，所以满足单调性。
当5是可行解，5之后的就不用找了，因为我们要找最小值，答案必然在5的左边，所以也满足二段性。
因此，这题能用二分。

因为我们要求下限，所以用的是求左边界的整数二分模板。

int l = 1, r = 100010;
int mid;
while (l < r) {
    mid = (l + r) >> 1;
    if (check(....)) {
        r = mid;
    }
    else {
        l = mid + 1;
    }
}

check函数是判断猜的答案是否满足题目要求

bool check(int x, int n, vector<int> &qua) {
    //满足的情况就是,每个店都只能分到一种商品，并且物品都能分完
    for (auto e : qua) {
        n -= e / x; // x是每个物品能分到的最大值，所以一分出去 
        if (e % x) n--; // 除不尽也要分给一个商店
        if (n < 0) return false;
    }
    return true;
}