二分答案

二分答案是一种充分利用答案的离散特性和问题的单调特性，用 $O(\log n)$ 倍的时间复杂度的代价将最优化问题转化为判定问题的思想。这句话有些抽象，我们通过一道例题来展示二分答案思想的运用。

例题

给定一个长度为 $n(1\leq n\leq 10^5)$ 的正整数数列和一个整数 $k$，要求将数列划分成连续的 $k$ 份 (形象地来说，将其切成 $k$ 段)，对每一段中的数求和，要求最大的和最小，并输出这个和。

这题困难的地方在于你很难确定第一刀切在哪里——如果切的太靠后，这一段的和本身可能就太大了；如果切的太靠前，后面的段可能包含的数过多，会导致后面的段的和太大。该题最优化的要求使得我们每一步既要瞻前也要顾后，从而难以下手。

我们利用这个问题来解释二分答案思想的合适使用场景：

• 答案的离散性：最终答案一定是一个 $[1, \sum a_i]$ 之间的整数，可选的答案是有限个。
• 问题的单调性：如果 $s$ 满足题目的要求，即存在一个划分方案满足最大和小于等于 $s$，那么所有大于 $s$ 的值都满足条件。在单调性的基础上，你可以看出 $[1, \sum a_i]$ 中的整数存在一个“分界线”，小于分界线的数都给不出划分方案 (无法成为答案)，大于等于该分界线的都可以给出划分方案。我们要找的就是这个“分界线”。

二分答案 (以原问题为最小化问题为例，最大化问题相反) 的框架如下

l, r, ans = 答案的下限, 答案的上限, 0
while l <= r:
    mid = (l + r) >> 1
    if check(mid): # mid 是合法的 
        ans = mid  # 作为备选答案
        r = mid - 1 # 尝试往左寻找更小的答案
    else:
        l = mid + 1 # “分界线”在右侧

在本问题中，通过二分答案，我们可以将每轮的问题转化为：是否存在一个划分方案，使得每段的和都不超过 $mid$？这个问题存在简单的贪心解法，我们尽可能让当前段容纳更多的数，直到再加入一个数就超过限制了的时候，我们划一刀开启新的一段。最终是否合法取决于能否用不超过 $k$ 段把所有的数容纳进来。

二分答案的外层框架提供了 $O(\log \sum a_i)$ 的代价，里面每一轮检查都是 $O(n)$ 的，因此总时间复杂度为 $O(n\log \sum a_i)$。