企业官网建设流程全解析

去年带训练队的时候，有个学弟拿着 POJ 3273 跑来找我，问了一个让我印象很深的问题：“学长，我明白二分查找，但为什么这道题也在二分？它到底在二分什么？”

这个问题几乎是每个刚接触二分答案的人都会卡住的地方。你背过二分查找模板，知道在有序数组里查一个数，但二分答案里既没有有序数组，也没有要查的目标值，看起来完全不是一回事。更让人头疼的是，同样是二分，有的题要求“最大值最小”，有的题要求“最小值最大”，光是把这两个方向搞清楚，就能劝退一大半新手。

这篇文章我想把二分答案这件事彻底拆开讲清楚，重点就是“最大”和“最小”这两类模型到底有什么区别、check 函数应该怎么写、二分边界应该怎么收缩，以及我在实际刷题和带训练过程中踩过的坑。不管你是准备 CSP/NOIP 的竞赛生、要应付机试的考研党，还是刷 LeetCode 面试题的选手，这套东西都值得花一下午彻底吃透。

1. 二分答案到底在“二分”什么

1.1 二分查找与二分答案：一字之差，对象完全不同

先说结论：二分查找的对象是数组下标，二分答案的对象是答案的取值范围。

二分查找的场景很固定：一个有序数组，你要找某个 target 的下标。每次取中间位置，比较大小，然后向左或向右收缩。它利用的是数组元素的“有序性”。

二分答案则完全不一样。它面对的问题往往没有一个现成的有序数组，只有一个让你摸不着头脑的问题，比如“把数组分成若干段，让最大值最小”。这时候你不需要直接去构造最优方案，而是去“猜答案”，再写一个函数来验证这个答案行不行。

我常用一个生活类比解释：你去批发市场买一批零件，卖家说单个成本在 100 到 200 块之间，你想知道最低谈到多少钱能保证质量合格。你不会让卖家把每个价格都试一遍，而是先报一个价，比如 150，问这个价能供货吗。能，就往下压；不能，就往上加。每报一次价，就是一个 check 过程。二分答案做的就是这个事。

所以二分答案的核心思想可以提炼成一句话：把“求最优解”转化成“判定一个值是否可行”。这也是它和普通二分查找最大的区别——前者在“猜答案”，后者在“找目标”。

1.2 把“求最值”翻译成“判可行性”

很多同学第一次接触二分答案时最大的障碍，是思维惯性。看到一个求最值的题，第一反应是先想怎么构造最优方案。但二分答案直接反过来了：我根本不需要知道最优方案长什么样，只需要能判断某个答案可不可行。

举一个最经典的例子。给你一个长度为 n 的数组，要求按顺序分成不超过 m 段，希望所有段的和的最大值尽量小。如果直接构造方案，你得考虑每一段从哪里断开，这本质上是个枚举切割点的组合问题，复杂度非常高。但如果你换一种问法：给定一个数 x，我能不能用不超过 m 段，让每一段的和都不超过 x？

这个问题就好答多了。我从左到右扫一遍数组，能塞进当前段就塞，塞不下就新开一段，最后数一数用了多少段。只要段数不超过 m，就说明 x 是可行的。

看到没有，整个思路的关键变化就在这里：从“构造最优解”变成了“验证某个解是否成立”。而验证往往比构造简单得多，因为它只关心“能不能做到”，不关心“具体怎么做到最好”。二分答案就是把这种“验证能力”利用到了极致——既然验证一个答案很容易，那我就在答案的范围里二分搜索，每次验证一下，最终逼近最优解。

2. 二分的前提：单调性决定一切

2.1 可行性随答案变化必须单调

不是所有求最值的题都能用二分答案，能用它有一个大前提：答案的可行性必须是单调的。

什么叫单调？我们拿两类典型问题来看。

第一类是“最大值最小化”。设答案为 x，x 越小代表要求越严格。x 很小的时候，方案几乎没法满足，check 返回 false；x 慢慢变大，约束变松，某一天开始 check 变成 true，之后一直保持 true。整个序列是 false、false、true、true、true……这种形态就是单调的。

第二类是“最小值最大化”。x 很小时，条件非常宽松，随便放都能满足，check 返回 true；x 越来越大，要求越来越苛刻，某一天开始 check 变成 false，之后一直 false。序列是 true、true、false、false……同样是单调的。

这个单调性决定了二分的可行性：你拿到一个 mid，如果它可行，你就可以判断最优解在 mid 的哪一侧；如果它不可行，又可以判断在另一侧。只要能这样不断缩小范围，最终就能锁定答案。

2.2 不单调会出现什么问题

有些同学可能会想：如果 check 函数本身写得不对，或者题目本身不具备单调性，二分还会生效吗？答案是不仅不生效，还会给出完全错误的答案。

假设一个题目的可行性序列是 true、false、true，你二分到中间那个 false 时，会以为答案在右侧，但实际上左侧也有可行值，于是正确答案就被错过了。这就是为什么写二分答案之前，一定要先在草稿纸上画一下：x 特别小的时候 check 是什么，x 特别大的时候 check 是什么，中间是不是连续过渡的。

我自己的习惯是拿到题先手算三个值：一个特别小的 x、一个特别大的 x、一个中间值。把这三个值的 check 结果写出来，如果发现它是 0/0/1 或者 1/0/0 这种非单调的情况，就说明这题不适合二分答案，得换思路。

还有一个容易踩的坑：有的同学以为二分答案要求“原数组有序”，这是错的。二分答案本身不依赖原数组顺序，但 check 里的贪心逻辑往往要求你先把数据处理成有序的，比如二分最大间距前要先给坐标排序。后面 POJ 2456 的例子里我会专门再强调这一点。

3. 最大与最小：核心模板与原理

3.1 最大值最小化：让“最重的那段”尽量轻

最大值最小化这类问题的典型问法是：“最大值最小”“最重的尽量轻”“最长的一段尽量短”“让最大的开销不超过多少”。碰到这种表述，你要马上反应过来，这是在二分“最大值”本身。

以 POJ 3273 Monthly Expense 为例。题目给了 n 天的每天开销，要求把这 n 天按顺序分成恰好 m 个月，希望“月开销最大值”最小，输出这个最小值。

首先确定二分对象：我们要猜的数就是一个“月开销上限 x”。然后用 check(x) 判断：在每个月开销不超过 x 的前提下，最少能分成多少段。

check 的写法很经典：

bool check(int x) { int cnt = 1; // 至少有一段 int cur = 0; // 当前段累计开销 for (int i = 1; i <= n; i++) { if (a[i] > x) return false; // 单日开销已经超过上限，直接不可行 if (cur + a[i] > x) { // 当前段放不下，开新段 cnt++; cur = a[i]; } else { cur += a[i]; } } return cnt <= m; // 关键：最少段数不超过 m 就算可行 }

这里有一个让很多人困惑的点：题目要求“恰好分成 m 段”，为什么 check 里判断的是cnt <= m而不是cnt == m？

原因很简单：如果最少只需要 cnt 段就能满足“每段和不超过 x”，那你完全可以把其中某些段再拆开，段数变多，但每段和依然不会超过 x。也就是说，只要最少段数不超过 m，就一定能通过拆分凑出恰好 m 段。反过来，如果最少段数都超过 m 了，那任何合法的 m 段划分都不存在。

完整的主函数二分部分：

int l = 0, r = 0; for (int i = 1; i <= n; i++) { l = max(l, a[i]); // 下界：单日最大开销 r += a[i]; // 上界：所有开销之和 } while (l < r) { int mid = (l + r) >> 1; if (check(mid)) { r = mid; // x 可行，试试更小的 } else { l = mid + 1; // x 不可行，必须放大 } } printf("%d\n", l);

注意初始下界为什么是数组最大值而不是 0。如果下界小于单个元素的最大值，check 里会直接因为a[i] > x返回 false，虽然二分也能一步步往上逼近，但会多跑很多无效迭代。直接从单日最大开销开始，能省掉一截搜索空间。

3.2 最小值最大化：让“最近的那对”尽量远

另一类是“最小值最大化”，典型问法是：“最小值最大”“最近的距离尽量远”“让最小的间隔越大越好”。POJ 2456 Aggressive Cows 就是这类题的代表。

题目说：有 n 个隔间，坐标给定，要把 c 头牛放进这些隔间，希望任意两头牛之间的最小距离尽可能大，输出这个最大化的最小距离。

同样先确定二分对象：我们要猜的数是“允许的最小间隔 d”。然后 check(d) 判断：在任意两头牛距离至少为 d 的前提下，最多能放几头牛。

check 的写法用贪心：

bool check(long long d) { int cnt = 1; // 第一头牛放最左边的隔间 long long last = x[1]; // 上一头牛的位置 for (int i = 2; i <= n; i++) { if (x[i] - last >= d) { cnt++; last = x[i]; } } return cnt >= c; // 关键：最多能放的牛数 >= c 就算可行 }

这里又有一个“为什么不是等于”的问题。题目要求放恰好 c 头牛，但 check 里判断的是cnt >= c。理由和上一题类似：如果间距 d 下能放下超过 c 头牛，那你随便挑其中 c 头放，最小距离仍然不小于 d，所以条件成立。反之，如果最多都放不满 c 头牛，那任何方案都无法满足。

另外注意第一头牛一定要放在最左边的隔间。这是因为放得越靠左，后续牛的选择空间就越大，不会损失可放数量。这是贪心成立的关键：局部最优选择能带来全局最优数量。

主函数二分部分：

sort(x + 1, x + n + 1); // 坐标输入顺序不定，必须先排序 long long l = 0; long long r = x[n] - x[1]; // 最大可能距离 while (l <= r) { long long mid = (l + r) >> 1; if (check(mid)) { l = mid + 1; // d 可行，试试更大的 } else { r = mid - 1; // d 太大，缩小 } } printf("%lld\n", r);

注意这题我用了while (l <= r)，和上一题的while (l < r)不一样。原因在于两类问题的答案存储位置不同：

• 最大值最小化：当 mid 可行时，正确答案可能更小，所以我们收缩右边界 r = mid，最后 l 就是答案。
• 最小值最大化：当 mid 可行时，正确答案可能更大，所以我们扩大左边界 l = mid + 1，但最后一次可行的 mid 会被保存在 r 中，所以循环结束后输出 r。

如果你觉得每次都要想“输出 l 还是 r”很晕，有一个更通用的写法：用一个 ans 变量记录最后一次成功的位置。

long long ans = 0; while (l <= r) { long long mid = (l + r) >> 1; if (check(mid)) { ans = mid; // 这个答案可行，先记下来 l = mid + 1; // 继续找更大的 } else { r = mid - 1; } } printf("%lld\n", ans);

这种写法虽然多一个变量，但逻辑非常清晰：每次 check 成功就更新 ans，循环结束后 ans 一定是最优解。我在实际做题时更推荐这个写法，可以少想很多边界问题。

3.3 一张表对比两种套路

为了让你一眼分清两类问题的差异，我把核心区别整理成一张表：

做题时先看题目问你的是“最小化什么”还是“最大化什么”，再去确定二分方向和 check 逻辑。这个判断比背模板重要得多。

4. 实战：拿到题目怎么快速套模板

4.1 五步拆题法

很多同学背了一堆模板，一到新题还是不会用。我总结了一个五步流程，每次拿到题都按这个顺序走：

1. 读题确定目标：把题目要求翻译成“我要最大化什么”或“我要最小化什么”。圈出题干里的“最大/最小”关键词。
2. 确定二分对象：找到那个被优化的参数。它通常就是你最后要输出的那个值。
3. 设计 check 函数：问自己一个问题——“如果我知道了答案 x，能不能在 O(n) 或 O(n log n) 时间内判断 x 是否可行？”这个问题的答案决定了二分答案能不能用。
4. 确定上下界：下界往小想，上界往大想，但可以结合题目数据缩小范围。比如数组最大值、坐标最大差值、所有元素之和等。
5. 写二分循环：根据“可行时往哪边收缩”确定模板方向，建议用 ans 变量记录中间成功结果，避免 l/r 输出混乱。

这五步里最容易出错的是第三步。很多人纠结模板细节，却忽略了 check 本身才是二分答案的灵魂——模板只是骨架，check 是大脑。

4.2 完整过一遍 POJ 2456

拿上面说的五步法，我们完整走一遍 POJ 2456。

第一步，读题。“最小距离尽可能大”，这是经典的最小值最大化。第二步，二分对象是“允许的最小间隔 d”。第三步，check 函数就是上面的贪心模拟：给定 d，最多能放多少头牛。第四步，上下界：下界取 0，因为距离至少为 0；上界取排序后最大坐标减最小坐标，因为不可能有更大的间隔了。第五步，可行时向右找更大值，用 ans 记录。

完整可提交的代码：

#include <bits/stdc++.h> using namespace std; const int N = 100010; int n, c; long long x[N]; bool check(long long d) { int cnt = 1; long long last = x[1]; for (int i = 2; i <= n; i++) { if (x[i] - last >= d) { cnt++; last = x[i]; } } return cnt >= c; } int main() { scanf("%d%d", &n, &c); for (int i = 1; i <= n; i++) scanf("%lld", &x[i]); sort(x + 1, x + n + 1); long long l = 0, r = x[n] - x[1], ans = 0; while (l <= r) { long long mid = (l + r) >> 1; if (check(mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } printf("%lld\n", ans); return 0; }

几个容易错的地方我再强调一下：

• 坐标输入未必有序，check 里的贪心必须按坐标从左到右扫描，所以进入二分前一定要sort。
• 第一头牛固定放最左隔间，cnt初始从 1 开始，不是 0。如果你从 0 开始，会少算一头牛，答案就会偏大。
• 数据范围允许的情况下，坐标用long long，避免l + r溢出。mid = (l + r) >> 1在极限数据下可能超出 int 范围，这是竞赛里很常见的隐性 bug。

4.3 完整过一遍 POJ 3273

再用同样的流程看 POJ 3273。

第一步，读题。“月开销最大值最小”，最大值最小化。第二步，二分对象是“每个月开销的上限 x”。第三步，check 函数：给定 x，按顺序贪心分段，最少能分成几段，判断是否不超过 m。第四步，上下界：下界取单日最大开销，上界取所有天开销之和。第五步，可行时向左找更小的 x，用 ans 记录。

完整代码：

#include <bits/stdc++.h> using namespace std; const int N = 100010; int n, m; int a[N]; bool check(int x) { int cnt = 1, cur = 0; for (int i = 1; i <= n; i++) { if (a[i] > x) return false; if (cur + a[i] > x) { cnt++; cur = a[i]; } else { cur += a[i]; } } return cnt <= m; } int main() { scanf("%d%d", &n, &m); int l = 0, r = 0; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); l = max(l, a[i]); r += a[i]; } int ans = 0; while (l <= r) { int mid = (l + r) >> 1; if (check(mid)) { ans = mid; r = mid - 1; } else { l = mid + 1; } } printf("%d\n", ans); return 0; }

这里最值得记住的，还是“最少段数不超过 m 就算可行”这个转化。很多人想不通为什么不是恰好等于 m，其实你把“拆段”这个操作想清楚就明白了：一组可以拆成两组，不影响每段和的上限，所以组数多一点也不怕，只要最少组数能压到 m 以内，后面随便拆都能凑出正好 m 段。

5. 竞赛与面试中的坑：我踩过的那些雷

5.1 方向判断错误：最大的坑

最常见的 WA 原因是方向反了。最大值最小化的题用了“可行就往右找”，最小值最大化的题用了“可行就往左找”，本来该输出 l 的地方输出了 r。症状就是样例能过，一提交就错。

我自己的排查方法很笨但有效：找一个很大的 x 和一个很小的 x，分别手算 check 结果。如果 x 很小时 check 返回 false、x 很大时返回 true，那题目方向就是“往左找最小可行值”；如果反过来，就是“往右找最大可行值”。只要这个方向判断对了，二分模板基本不会错。

5.2 二分死循环：模板写法不匹配

while (l < r)配l = mid或者r = mid时，如果 mid 的取整方向没配好，很容易死循环。比如区间收缩到 l = 2、r = 3 时，mid = 2，如果 check(2) 为 true 且你写了l = mid，那么 l 永远停在 2，循环就出不来了。

我推荐一个绝对稳妥的写法：不管哪类问题，都用while (l <= r)，并且每一步都执行l = mid + 1或r = mid - 1。因为 mid 每次都被排除出区间，区间长度严格递减，绝不可能死循环。再配合 ans 记录答案，基本万无一失。

5.3 溢出与数据范围

二分答案经常涉及数组总和、坐标差、最大距离这类数值，很容易逼近 int 上界。比如数组 n = 1e5，每个数 1e9，总和就是 1e14，int 早就爆了。我早期写 POJ 3273 时就用 int 存总和，结果 WA 了一晚上，换成 long long 马上过了。

另一个细节是mid = (l + r) / 2时，l + r 可能溢出。虽然很多题数据没那么极限，但保险起见推荐写成mid = l + (r - l) / 2，或者直接用long long。

5.4 check 内部细节：贪心写错

check 的问题往往藏在细节里。

POJ 3273 的 check 里，cnt初始为 1，因为无论如何至少有一组。如果你写成 0，最后判断cnt <= m时会多算一组，导致结果偏小。

POJ 2456 的 check 里，第一头牛固定放最左端，cnt初始为 1。如果你漏掉第一头牛，从 0 开始数，那结果会偏大。

还有一点：check 里要处理单点超过上限的情况。比如 POJ 3273 里如果某一天的开销本身大于 x，那这个 x 无论如何不可行，直接返回 false。这个判断漏掉的话，贪心会把这一天单独成段，仍然可能得到 cnt <= m 的错误判断。

5.5 实数二分的精度控制

有些二分答案题要求输出浮点数，比如“最小半径”“最短时间”的浮点版本。这时候用 while (r - l > eps) 很容易踩精度坑：eps 设大了，答案不够精确；设小了，循环跑不停。

更稳的做法是固定迭代次数，比如跑 100 次：

double l = 0, r = 1e9; for (int i = 0; i < 100; i++) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } printf("%.10f\n", l);

100 次迭代的精度远远超过 double 能表达的范围，而且绝对不会死循环，是竞赛里最省心的写法。

5.6 问题速查表

6. 进阶：二分答案的玩法不止两种

6.1 二分答案 + 贪心 / DP / 差分

二分答案最常见的是搭配贪心，前面两道题都是这种组合。但 check 内部不一定是贪心，也可以配合其他算法。

当贪心不成立时，可以在 check 里用动态规划。比如某些划分问题，状态转移里需要判断段和是否满足当前二分的上限，用一维 DP 就能完成验证。虽然复杂度比纯贪心高，但二分的 O(log W) 因子通常可以接受。

还有一种高频组合是二分答案 + 差分数组。典型场景是：给定若干区间操作，问你最少操作多少次能让某个最值达标。你把“操作次数”二分掉，然后在 check 里用差分数组模拟全部操作，O(n) 内判断是否可行。这类题在思维题和模拟题里出现频率很高。

6.2 二分答案 + 数据结构

如果 check 里需要动态维护一些信息，比如区间最值、出现次数、前缀和等，可以配合线段树、树状数组或平衡树来写。整体复杂度会变成 O(n log n log W)，在 n 比较小的时候依然可跑，面试题里偶尔会出现这种组合。

我处理这类题的经验是：先把 check 的朴素写法想清楚，再考虑用数据结构优化。很多人一上来就套线段树，结果 check 逻辑本身都是错的，后面全是白搭。

6.3 实数域二分与三分

实数域二分的写法上面已经给过，固定 100 次迭代是无脑选。三分法则用于单峰函数求极值，和二分答案的“单调边界”是两种不同思路。前者找峰值，后者找 0/1 边界。这个区别想清楚，就不会把三分的题硬套二分答案。

我自己带训练这几年，见过太多同学把模板背得滚瓜烂熟，一到新题就分不清往左还是往右。后来我教他们一个笨但有效的自检方法：先别写代码，找三个 x——一个特别小、一个特别大、一个中间值——手算 check 结果，把 true 和 false 串起来。如果你能写出一个像 0/0/1/1 或 1/1/0/0 这样单调的序列，这题就稳了；如果写出来是 1/0/1 这种形状，那赶紧换思路。

二分答案表面上考的是二分，实际上考的是你会不会写 check，以及你敢不敢把“求最优”换成“猜答案”。这个思维一旦转过弯，后面看很多题都会通透不少。我到现在写新题时还会下意识问自己一句：如果我知道答案，能在 O(n) 内验证吗？能，就值得往二分答案上想。