企业官网建设流程全解析

做算法题这些年，有个技术点让我印象特别深：二分答案。第一次在题目上看到“二分答案”这个标签时，我其实挺懵的——二分查找我熟，有序数组里找值嘛，但“二分答案”是什么？答案还能二分？后来在洛谷上把两道经典题亲手写明白，才彻底搞懂这个套路。这篇文章就把我从理解到掌握的全过程记录下来，适合刚学完二分查找、正准备进阶二分答案的读者，也适合刷题时碰到“最大值最小”“最小值最大”这类描述就头皮发麻的同学。

1. 先把“二分答案”是什么讲明白

1.1 它和普通的二分查找差在哪

普通二分查找，针对的是数组。数组有序，你拿着目标值，每次通过比较中间元素来排除一半范围，最后定位到元素下标。整个过程的核心是“在一个已知集合里找一个精确的值”。

二分答案不太一样。它二分的不再是数组下标，而是一个“答案区间”。这个区间往往是一个连续的整数范围，比如“锯子的高度”“最短跳跃距离”“最大载重”，你需要在这个区间里找到那个满足条件的“最优解”。

这里的难点是：最优解不能直接算出来，只能靠“试”。怎么试？给定一个候选答案x，你写一个函数能快速判断它是否可行，如果可行，你再往大的试（或者往小的试），不可行就往反方向试。这个“试”的过程，因为每次排除一半的区间，所以效率很高。

生活里有个很贴切的例子：猜价格。主持人心里想一个数字让你猜，你每猜一次，他只告诉你“高了”还是“低了”。你肯定不会从1块开始一块一块往上加，而是直接报500，听完反馈后把范围砍半，再报250或者750。二分答案干的就是这件事：每个候选答案，相当于你猜的一个价格；“可行”还是“不可行”，相当于主持人告诉你“低了”还是“高了”。只不过这个“主持人”是你自己写的一个check函数。

1.2 单调性：二分答案能成立的根基

聊到这里，你可能会问：是不是随便猜个区间都能二分？当然不是。二分的前提是“可行性必须随着答案单调变化”。用猜价格举例，主持人心里想的那个数，你往高了报他不说“高了”，往低了报他也不说“低了”，那这个游戏就没法玩。

算法的道理一模一样。假设我们要找最大的可行答案x，那么x小时时候可行，x大的时候不可行，中间一定有一个临界点。这个临界点就是最优解。反过来，如果你要找的是最小的可行答案，那x小的时候不可行，x大的时候可行，临界点同样是最优解。

这就是二分答案的全部思想基础。后面两题的check函数，本质都是在验证一件事：给定这个候选值，题目条件成不成立。而这个“成立”随候选值的单调变化，就是我们敢用二分的底气。

2. 第一题：砍树，一个模板吃透最基础用法

2.1 题意拆解：为什么答案是二分出来的

砍树这道题非常经典，它来自洛谷的P1873（EKO），题目大意是：

有n棵树，每棵树有个高度。现在你要定一个锯子的高度H，锯子会砍掉所有高于H的部分，把这些砍下来的木材收集起来。你至少需要m米的木材，问H最大能取多少。

举个例子：三棵树高度分别是5、10、15，你定H=10，那么只有第三棵树会被砍掉5米，总木材是5米。如果你定H=5，三棵树砍下来分别是0、5、10，总共15米。但H太高的话，可能一棵树都够不到，木材直接是0。

注意这里问的是“H最大能取多少”。H越大，木材越少，越难满足“至少m米”的需求；H越小，木材越多，越容易满足。所以如果定义check(x)为“锯子高度为x时，能不能砍到至少m米的木材”，那么check(x)的结果是：x小的时候成立，x大的时候不成立。我们要找的就是那个“仍然成立的最大x”。

为什么不直接算？因为你没法通过公式一步求出H。虽然每棵树的贡献是max(0, h[i]-x)，但你要反推x，没有一个简单的求逆运算。而验证一个x是否可行，只需要遍历一遍所有树，O(n)搞定，非常快。

2.2 判定函数 check 这样写

check函数的逻辑特别直白：给定一个高度x，把所有树高于x的部分加起来，看看总木材是否大于等于m。

bool check(long long x) { long long sum = 0; for (int i = 1; i <= n; i++) { if (h[i] > x) sum += h[i] - x; if (sum >= m) return true; // 已经够了，提前返回 } return sum >= m; }

这里有一个细节很多人会忽略：sum的类型必须用long long。假设有10万棵树，每棵树高10亿，H取0，那sum理论上能到10的14次方，int根本装不下。竞赛题里这个坑特别隐蔽，样例能过，一提交就WA（答案错误），十有八九就是类型爆了。

第二个细节是提前返回。当sum累计到超过m，可以直接return true，没必要继续遍历。这个优化在大数据下能省不少时间，尤其是当答案偏小，木材很快就能凑够的时候。

2.3 二分框架与完整代码

二分答案的框架和二分查找长得像，但有细微差别。强烈建议初学者用“ans记录法”，也就是二分循环里只要check通过，就把当前mid记录到ans里，最后直接输出ans。

为什么这么做？因为当check(mid)成立时，mid可能是答案，也可能答案比mid更大，反正mid是“目前已知的可行解里最好的”。你把它记下来，万一下一次查找的mid不可行，你还有上一次的可行解保底。这样比最后输出l还是r更不容易出错。

砍树这题的l和r取值是：l=0，表示锯子高度为0（所有树全砍）；r=最高那棵树的高度，因为锯子高度只要超过最高树，一棵树都砍不到，木材必定为0，显然不成立。答案一定在[0, maxH]这个区间里。

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

这个模板的循环条件是l <= r，每次l和r更新时都各自加1或减1，所以不会出现死循环。又因为mid总是落在[l, r]区间内，且每次check之后区间都会缩小，所以循环必终止。

2.4 这一题最容易犯的错

我第一次写这道题的时候，把l初始化成了1，结果样例里有一组答案是0的情况，直接输出错误。原因就是：如果m特别大，锯子高度必须低到0才能凑够木材，那答案就是0。l从1开始，mid取不到0，自然错了。所以上下界一定要覆盖完整答案区间，这是二分答案最容易翻车的地方。

还有一个很多人问过的问题：为什么答案范围不是从1到10^9枚举，要用二分？你可以算一下：n=10^5，如果从maxH往下每减1就做一次check，最坏要操作10^9次，肯定超时；而二分只做约log2(10^9)≈30次check，每次O(n)，总共300万次操作，轻轻松松过。

3. 第二题：跳石头，判断函数从“算”变成“模拟”

3.1 题目转化：最大最小距离怎么判

搞定了砍树，二分答案的框架算是入门了。但只做砍树，还体会不到二分答案的精髓，因为砍树的check函数就是一个简单的求和。第二题跳石头（NOIP原题P2678）才是真正考验思维的地方。

题目大意：从起点到终点有一条河，起点位置是0，终点位置是L，中间有n块石头，每块石头在距离起点d[i]的地方。现在你可以移走最多m块石头，移完之后选手要从起点踩着石头跳到终点，问你“移完之后任意相邻落脚点（含起点终点）之间的最小距离”最大能是多少。

“最小距离最大”，这种描述一出现，基本就是二分答案的信号。原因是：如果你把“最小距离”定成一个候选值x，那么“能不能通过移走不超过m块石头，让所有相邻石头间距都不小于x”这件事，是一个非常好验证的判定问题。而且可行性随x单调变化：x小，当然容易满足；x变大，需要移走的石头越来越多，一旦超过m，就不可行。我们要找的，就是临界点上那个最大的可行x。

3.2 check 的贪心模拟过程

这道题的check函数不再是求和，而是用一个贪心的模拟过程。

假设我们正在验证“最小距离至少为x”是否可行。核心思路是：从左往右遍历每一块石头，尽量保留离起点近的石头。我们从起点出发，维护一个变量last，表示“上一块被保留的石头的位置”。遍历每块石头，如果当前石头和last的距离小于x，说明这块石头和上一块保留石头的间距不够，那当前这块石头必须被移走，此时计数器cnt加1；否则，这块石头可以保留，把last更新为当前石头的位置。

为什么这个贪心是对的？因为如果当前石头和上一块保留石头距离不够x，那当前石头无论如何都不能保留——留着它只会徒增一个过近的相邻距离，而且它不会帮助后面的石头更近，所以移走它是最优决策。

这里有个坑：循环结束后，还要检查终点到last的距离。因为终点是固定位置，不能被移走，如果终点和最后一块保留石头之间的距离小于x，那这个x是不可行的。注意，这个坑太经典了，很多人循环里写得挺顺，结果忘了终点，直接白给。

bool check(int x) { int cnt = 0, last = 0; for (int i = 1; i <= n; i++) { if (d[i] - last < x) cnt++; else last = d[i]; } if (L - last < x) return false; return cnt <= m; }

注意这里的返回值。如果终点距离不够，不管cnt是多少，都直接return false，因为终点没法移走。如果终点距离够，再判断移走的石头数量cnt是否没超过m。两者都满足，这个x才成立。

3.3 完整代码和边界处理

二分区间上，l可以设为1，因为最短距离至少是1（都是整数点，距离不会小于1）；r设为L，因为最大最小距离不可能超过起点到终点的总长度。但如果你为了稳妥，也可以把l设成0，答案区间就变成了[0, L]。实测下来这两种都没问题，但习惯上我把l设成1能少一次判断。

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

这道题有个地方比砍树更好玩：check函数里的“移走”是虚拟的，你并没有真正修改数组。每次二分出一个mid，都重新从0开始模拟。因为二分的次数很少，每次模拟O(n)，整体效率非常高。这比你想一个真正的“移除方案”去求答案要容易太多。

3.4 两道题放在一起看：check 的两种形态

把砍树和跳石头放在一起看，你会发现二分答案的代码框架几乎一模一样，变的只是check函数里的逻辑。砍树的check是“直接计算总量”，跳石头的check是“贪心模拟过程”。

这两种形态可以覆盖绝大多数二分答案题目：

• 计算型：给你一个可行值x，你直接算出某个总量或指标，再和限定值比较。比如砍树、木材加工、月度开销这类。
• 模拟型：给你一个可行值x，你按照某种贪心策略去装、去分、去跳，看最终能不能满足约束。比如跳石头、进击的奶牛、数列分段。

所以你看，学二分答案本质上是在学两种东西：一是学会判断能不能用二分，二是学会针对题目设计check函数里那个“贪心/计算”逻辑。框架永远是那个框架。

4. 提炼成通用套路：从两题上升到模板

4.1 什么时候能想到二分答案

我见过不少同学，看完题解觉得二分答案好简单，可一到自己做题就想不到。其实二分答案的题目特征非常明显，你可以在做题时用一个四步判断法：

第一步，题目问的是最大值或最小值。尤其出现“最大值最小”“最小值最大”“某个值最大是多少”这类字眼。

第二步，答案落在某个连续的整数区间内，而不是某个离散的集合里。

第三步，存在一个check函数，能在多项式时间内验证一个候选答案是否可行。

第四步，check的结果随答案单调变化。单调递增或单调递减都行，但必须单调。

如果以上四条都满足，那基本就能锁定二分答案。还有一些间接的信号，比如题目数据范围特别大（1e5以上），而且你发现除了枚举答案外没有别的直观思路，那也该往二分答案上想一想。

4.2 一个通用模板和两个方向

二分答案的代码模板，我推荐下面这种“ans记录法”，它是我实测踩过各种边界坑之后最稳的写法：

int l = 0, r = INF, ans = 0; while (l <= r) { int mid = (l + r) / 2; if (check(mid)) { ans = mid; l = mid + 1; // 往更大的答案方向试 } else { r = mid - 1; // 答案太大了，往小的方向试 } } printf("%d\n", ans);

这套模板适用于“找最大的可行解”，也就是check(mid)为true时我们要向右收缩。至于“找最小的可行解”，只需要在check(mid)为true时把r = mid - 1，并记录ans即可：

while (l <= r) { int mid = (l + r) / 2; if (check(mid)) { ans = mid; r = mid - 1; // 往更小的答案方向试 } else { l = mid + 1; // 答案太小了，往大的方向试 } }

这两个方向只要想清楚你需要的是“更大”还是“更小”，就不会写反。如果实在拿不准，就在纸上画一条数轴，标出可行域在哪一侧，闭着眼都能写对。

4.3 mid 的取整方向和死循环问题

有些同学习惯用l < r的写法，也就是：

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

这个写法有个著名的坑：当check(mid)成立时，你执行l = mid；但如果mid恰好等于l，而l又小于r，那l永远不变，就死循环了。比如l=3，r=4，mid=(3+4)/2=3，check(3)成立，l还是3，区间永远不缩。

解决方法是把mid改成(l + r + 1) >> 1，向上取整。这也是为什么很多人说“整数二分要加1”。我个人的建议是：新手期老老实实用l <= r加ans记录的写法，它天然避开死循环问题，少受罪。等你用熟了，再回头尝试l < r的写法也不迟。

5. 实操避坑记录：这些细节害我调了半天

5.1 check 里提前返回的坑

砍树的check里，sum够了可以提前return true，这个优化安全且高效。但并不是所有check都能这么干。跳石头这种需要完整模拟的题目，如果你在遍历途中发现cnt已经超过m，可以提前return false，因为再往后遍历cnt只可能增加，不可能减少。

但是有一种情况千万别提前返回：如果check函数后半部分还依赖前面累计的状态，而你提前跳出了，就会漏掉关键判断。比如跳石头，你如果在循环里发现cnt超过m就提前返回false，这没问题；但你如果在终点距离还没判断时就提前return true，那就大错特错了。我见过有人把砍树的提前返回习惯搬到跳石头里，结果终点判断被跳过，WA得莫名其妙。提前返回的原则是：确认影响最终结论的信息已经全部处理完，才可以提前跳。

5.2 上下界设置不当直接错

二分答案的上下界是另一个高频出错点。上界太大会导致多出无效二分，但通常不会WA；真正致命的是下界设置得太高，导致正确答案被排除在区间之外。

砍树那题，如果你把l设成1，而答案是0，结果就会错。跳石头那题，如果你把l设成1而实际答案可能是0（所有石头都可以被移走，但终点距离仍然存在，仔细想想其实答案最小是1，但如果你是移走所有中间石头后，起点到终点距离L，最短距离仍是L，所以答案一定是正数）。这种边界分析必须具体题目具体处理。

我的习惯是：先把答案可能的最小值写出来（常常是0或1），再把答案可能的最大值写出来（常常是题目里的某个上限，比如最高树高、总长度、最大载重），然后把这两个值分别赋给l和r。宁可范围稍微大一点，也不要漏掉正确答案。

5.3 常见问题速查表

最后整理一个自查清单，每次写完二分答案可以对照检查一遍，基本能解决九成的问题。

还有一个调试小技巧：当你怀疑是二分答案的问题时，可以在二分循环里输出l、r、mid和check(mid)的结果，手动跑一遍小数据，看看区间收缩的方向是否正确。很多时候不是模板的问题，而是check的方向写反了，一输出立马就能看出来。

我个人在两题刷完之后最大的体会是：二分答案并不是什么高深技巧，它只是把“求解”换成了“判定”，再用单调性让判定的次数变成log级别。你真正要练的，其实是两件事：一是判断题目能不能二分答案，二是为自己的题目写出那个正确的check函数。这两件事熟练了，二分答案就是一个顺手就能用的套路，后面的粉刷匠、数列分段、月度开销等题目也都是一路通吃。如果你正在学这个套路，别急着背模板，先打开编辑器把砍树和跳石头亲手敲一遍，敲完你自然就懂我说的意思了。