# 二分答案（Binary Search on Answer）图解：最早什么时候够用？

拖动时间，看并行机器完成产品、产量阶梯跨过需求线；再让二分窗口逼近第一个可行时刻，理解为什么先证明单调性。

原文 / Canonical: https://crazycloud.cc/learn/binary-search-on-answer
作者: crazycloudcc
首次发布: 2026-10-10
更新: 2026-10-18

本阅读版与网页共用课程数据；互动请访问原文。

## 一句话答案

二分答案把优化问题改成判定问题：不直接猜最优答案，而是问某个候选值是否可行。如果真假结果只有一次分界，就能每次排除一半候选范围，找到第一个可行值。这里搜索的是完成需求的最早整数秒数，不是数组里某个值的下标。

## 适用条件与边界

机器从 0 秒同时开始、互不干扰，每台生产一件需要固定的正整数秒；只计算完整产品。需求是非负整数，机器至少一台。实验限制 1–4 台、每台 1–12 秒、需求 0–24 件，确保 JavaScript 整数精确且图形可读。一般算法不受此图形范围限制，但必须重新验证整数上界与溢出。

## 不变量

最早可行时间始终在 [lo,hi] 内。hi 本身可行；lo 可以可行，也可以不可行。每次比较后缩小区间，直到 lo=hi。

## 逐步例子

1. 先确定搜索空间：候选值 t 是经过的整数秒。每台耗时 kᵢ，t 秒内完成 floor(t / kᵢ) 件；总量 C(t) 是各台之和。enough(t) 判断 C(t) ≥ target。
2. 说明单调性：时间增加时，每台已完成的件数都不会减少，所以 C(t) 非下降。某时刻已经够用，所有更晚时刻都够用；某时刻不够，所有更早时刻都不够。
3. 用最快机器独自完成全部需求给出上界 U = min(kᵢ) × target。设 lo=0、hi=U，保持最早可行答案位于闭区间 [lo, hi]；这里不要求 lo 不可行。
4. 取 mid=lo+floor((hi-lo)/2)。若够用，hi=mid，保留这个可能最早的答案；否则 lo=mid+1，因为 mid 及更早都不行。lo<hi 时窗口严格缩小；相等时返回 lo。
5. 示例机器耗时 [2,3,7]，需求 8 件，上界 16。检查 8 秒：4+2+1=7，不够，区间变 [9,16]；检查 12 秒：6+4+1=11，够，变 [9,12]；检查 10 秒：5+3+1=9，够，变 [9,10]；检查 9 秒：4+3+1=8，够，合拢到 9。
6. 确认最优性：9 秒完成 8 件，8 秒只有 7 件，因此最早是 9 秒。若需求为 0，答案直接是 0；两台同为 4 秒、需求 7 件时，12 秒只有 6 件，16 秒有 8 件，答案为 16。

## 复杂度与整数边界

n 台机器，上界 U=min(kᵢ)×target。每次判定 O(n)，二分 O(log(U+1)) 次，总时间 O(n log(U+1))，算法额外空间 O(1)（不含输入）。需求为 0 可直接返回 0。图形为探索时间预计算参考边界、保存步骤和画产量阶梯，有独立展示开销，不能当作二分运行时间。C++ 示例的 kᵢ、target 至多 10⁹，上界至多 10¹⁸，用 long long；累计产量提前截断，防止溢出。

## 常见误区

- 把要搜的时间误当成机器数组下标。机器耗时不需要排序；这里依赖的是 enough(t) 的单调性。
- 看见 true 就立即返回。它只说明这个时间够用，不代表最早；要令 hi=mid 继续向左找。
- 把这里的 hi=mid 与原二分查找的 hi=mid-1 混用。查第一个 true 与查相等元素维护的目标不同；循环条件、区间含义和更新必须成套。
- 没有证明单调性就套模板。[F,T,F,F,T,T,T,T] 在中点看到 F 并不能排除左边的 T。
- 把尚未做完的产品算成件数，或让动画插值改变算法状态。产量用向下取整；画面可连续变化，但二分只检查整数秒。
- 直接累加所有机器在大上界下的产量可能溢出。判定只需要知道是否够用，可在达到目标前提前返回；零耗时会除零，必须拒绝。
- 没有真实数组，也能用标准库：C++20 的 std::views::iota(0LL, U + 1LL) 表示候选整数 [0,U]，无需预存数组；这里 U 为 long long，且 0≤U≤10¹⁸。std::ranges::partition_point 要求谓词先 true 后 false（两段均可为空），所以本课传入 !enough(t)。先判断返回迭代器是否等于 end：相等表示该候选区间内无解，否则才把 *it 用作答案。仍须证明单调性、避免判定溢出，并确保排他上界 U+1 可表示。本课显式写循环是为了展示区间不变量。

## 自测

两台机器都需要 4 秒一件，需求 7 件。12 秒够吗？最早多少秒？如果需求为 0 呢？

12 秒每台 3 件，总共 6 件，不够。16 秒每台 4 件，总共 8 件，最早 16 秒。需求为 0 时，最早 0 秒；无需启动生产。

## 可选进阶：固定其他参数，寻找最后一个可行公差

2026-10-17结束的AtCoder ABC480 E要求统计：长度至少3、首项与公差均为正整数、所有项的乘积不超过N的等差数列。先固定首项a和长度m，只让公差d变化。各项为a、a+d、…、a+(m−1)d；d增大时每项都不减且后面的项严格增大，所以乘积严格增大。谓词‘乘积≤N’先true后false，我们要找最后一个true，与上方机器实验寻找第一个true的方向不同。

例如固定N=120、a=1、m=3：d=7时是1、8、15，乘积120刚好可行；d=8时是1、9、17，乘积153不可行。由单调性，正公差1到7全可行，这组首项和长度贡献7种数列；它不是整道题的总数18。只要固定参数下d=1就不行，该组贡献便是0。

对原题N≤10¹⁸，可用lo=0作‘尚无正公差解’的哨兵、hi=10⁹作不可行哨兵；hi处仅前三项的乘积就至少为1×(1+10⁹)×(1+2×10⁹)>10¹⁸。保持正公差答案在lo及hi之间的分界：hi−lo>1时取下中点，若可行令lo=mid，否则hi=mid；结束返回lo。lo=0不是真实允许的公差，也不要求代入谓词成立。不能照搬机器实验里“可行则hi=mid”的分支，更不能用lo=mid却保留lo<hi的循环条件。

不用先算巨大乘积：令q=N，依次对每个正整数项v做q=floor(q/v)，最后q>0恰好等价于所有项的乘积≤N。这利用连续向下取整的整数除法等于对总乘积向下取整；中途q变0后可直接判不可行。例中120÷1÷8÷15依次向下取整得1，120÷1÷9÷17则得0。整数项的生成和N本身也必须精确；JavaScript原题范围应使用BigInt，不能先用Number算完再转换。

完整计数还要枚举首项和长度：a³≤N给出a≤10⁶，最小长度m的正整数递增数列乘积至少m!，而20!>10¹⁸，所以只需m=3到19。每组固定参数的最大可行公差就是这一组的数量，再求和；这一页只解释二分判定的迁移，不把单次二分冒充整题算法。上方SVG、交互和同步代码仍只演示机器生产时间，不模拟这些大整数等差数列。

## 延伸学习

换一个搜索空间：在有序 tails 中找第一个 ≥ x 或 > x 的位置。若不存在就返回 end 并追加，而不是返回一个可解引用的元素；这与本课已有可行 hi 的前提不同。

[相关应用：LIS 中的 lower_bound 与 upper_bound](https://crazycloud.cc/learn/longest-increasing-subsequence)

## 参考资料

- [AtCoder ABC480 E：Product-Bounded Arithmetic Sequences（赛后进阶）](https://atcoder.jp/contests/abc480/tasks/abc480_e)
- [AtCoder ABC480 E 官方题解：固定参数与乘积判定](https://atcoder.jp/contests/abc480/editorial/27231)
- [CP-Algorithms：单调谓词与二分答案](https://cp-algorithms.com/num_methods/binary_search.html#search-on-arbitrary-predicate)
- [USACO Guide：Binary Search on Monotonic Functions](https://usaco.guide/silver/binary-search)
- [CSES：Factory Machines（并行生产问题；本站另设教学示例）](https://cses.fi/problemset/task/1620/)
- [AtCoder 官方题解：C++20 iota 与 partition_point](https://atcoder.jp/contests/abc319/editorial/7115)

[返回图解实验室](https://crazycloud.cc/learn)