二分答案算法精讲：从河中跳房子问题理解最值优化

1. 从“河中跳房子”到二分答案一个经典思维的诞生如果你刚开始接触算法竞赛或者刷题看到“1247河中跳房子”这个标题可能会觉得有点摸不着头脑。这听起来像是个游戏或者物理题怎么就成了经典的算法例题我第一次遇到它时也有同样的疑惑但真正动手做下来才发现这道题简直是理解“二分答案”这个核心思想的绝佳敲门砖。它没有复杂的图论结构也没有繁琐的动态规划状态转移就是用一个最朴素的场景逼着你去思考一个根本问题当答案本身难以直接求解但给定一个“候选答案”后我们能快速判断它是否可行时我们该怎么办“河中跳房子”描述的场景非常直观有一条河河中间有N个石头房子它们与起点的距离是已知的。现在我们要从起点跳到终点每次跳跃必须落在石头上并且跳跃距离不能小于一个给定的值。问题是在必须移走恰好M块石头的情况下如何安排移走哪些石头使得最终能够完成跳跃的最短跳跃距离尽可能大这个“尽可能大的最短跳跃距离”就是我们要求解的答案。为什么这个问题适合用二分答案因为答案——那个最短跳跃距离——是一个整数并且存在一个明确的边界。想象一下如果允许的跳跃距离非常小比如1那么你几乎可以踩着所有石头过去移走M块石头后肯定也能过去所以这个答案是“可行”的。如果允许的跳跃距离非常大大到超过相邻石头间的最大间隔那么你移走M块石头后必然存在一段你跳不过去的空隙所以这个答案是“不可行”的。于是在“可行”与“不可行”之间存在一个临界点。我们的目标就是找到这个最大的、依然可行的跳跃距离。手动去猜这个数显然效率低下而二分查找正是用来在有序范围内快速定位这种临界点的利器。网络上相关的热词如“二分答案”、“二分查找”、“贪心算法”都指向了这里。很多人学二分只记住了在有序数组里找某个数却不知道“二分答案”才是二分思想更具威力的应用。这道题就是一个完美的桥梁它要求你跳出“在给定序列中查找”的定式思维转而去在一个答案的可能区间里利用一个判断函数来缩小区间。这个思维模式的转换是解决一大批最优化问题的关键从安排会议时间到分配资源其内核都是相通的。2. 问题拆解定义、约束与核心挑战在动手写代码之前我们必须把题目嚼碎了咽下去理解每一个条件背后的意图。这不仅仅是读懂题目更是为了设计出正确的“可行性判断”函数这是二分答案的灵魂。2.1 问题要素的精确翻译首先我们把生活化的描述翻译成程序员熟悉的语言输入河的长度L起点到终点的距离石头数量N不包括起点和终点必须移走的石头数M以及N块石头距离起点的位置升序给出。隐含点起点位置0和终点位置L是固定的不能移动。我们跳跃的“舞台”就是由起点、终点以及剩下的 (N - M) 块石头构成的。动作从起点开始每次跳到下一块剩余的石头最终跳到终点。每次跳跃的距离就是两块石头位置之差。目标在移走恰好M块石头后找出一种保留石头的方案使得所有跳跃距离中的最小值最大。输出这个最大的最小值。这里有一个非常关键的理解点我们不是要找出移走哪M块石头而是要找到一个最大的距离D使得存在一种移走M块石头的方法让剩下的石头包括起点终点中任意相邻两块的距离都至少为D。前者是一个具体的组合方案后者是一个数值目标。二分答案帮我们找到的是后者。只要我们能判断某个D是否可行我们就能用二分逼近最大的那个D。2.2 为什么贪心算法是可行性判断的“最优解”给定一个候选的“最短跳跃距离”D如何判断在移走不超过M块石头的前提下能否实现所有跳跃距离都 D一个最直接的思路是模拟跳跃过程。我们从起点位置0开始看向下一块石头。如果当前石头与下一块石头的距离 D那么我们可以安全地跳过去并把下一块石头作为新的起点。如果距离 D说明这块石头太近了如果我们不跳过去就无法到达终点因为我们必须按顺序跳。那么唯一的办法就是移走这块距离太近的石头然后继续比较当前石头与再下一块石头的距离。这个过程天然就是一个贪心算法我们在每一步都做出局部最优选择——只要石头够远就跳过去不够远就移走它。为什么贪心在这里是正确的因为我们的目标是让所有间隔 D并且希望移走的石头尽可能少。如果当前石头和下一块石头距离小于D保留下一块石头必然导致这段间隔不达标。移走它是为后续的间隔创造可能让当前石头直接对接更后面的石头。这个决策只影响当前这一段不会对未来的决策产生后效性因此贪心是有效的。具体判断函数check(D)的逻辑如下初始化last_pos 0起点位置removed 0移走石头计数。遍历每一块石头位置为stone[i]计算stone[i] - last_pos。如果距离 D说明石头i太近必须移走removed。如果距离 D说明可以跳到石头i更新last_pos stone[i]。遍历结束后不要忘记终点计算L - last_pos最后一块保留的石头到终点的距离。如果这个距离也 D那么意味着即使调整石头从最后一块石头也无法跳到终点这个D肯定不可行。实际上在贪心过程中如果最后一段距离小于D我们已无石头可移终点不能移所以直接判定不可行。判断removed M。如果成立说明用不超过M次的移除操作可以实现所有跳跃 DD是可行的否则不可行。注意这里有一个非常重要的细节也是容易出错的地方。check(D)函数判断的是“能否在移走不超过M块石头的情况下实现条件”。题目要求是“移走恰好M块”那会不会有“移走少于M块就能满足条件导致我们找到的不是题目要求的解”的情况实际上如果某个D满足“移走 M 块石头即可”那么它一定是可行的。因为我们可以通过额外移走一些无关紧要的石头比如在已经很远的间隔中间再移走一块凑足恰好M块而这并不会降低已有的最短跳跃距离。所以check(D)的条件是宽松的这保证了二分过程的正确性。我们最终找到的是满足“移走 M 块石头即可”的最大D它必然也对应着一种“移走恰好M块石头”的方案可以通过额外移除来凑数。3. 二分查找的边界与循环设计避开死循环的坑理解了check(D)我们就有了在答案空间里导航的指南针。接下来我们需要确定搜索的起点和终点并设计一个永不迷路的二分循环。3.1 答案边界的确定答案最短跳跃距离的最大值最小是多少理论上可以是0但0没有实际意义且我们的判断函数在D0时总是成立。更实际的下界是1。答案最大是多少一种朴素的认为是河的长度L但显然不可能跳那么远。一个更紧的上界是L本身如果你能一脚从起点跳到终点。但在二分时我们通常设置一个安全的、肯定不可行的上界。因为当D大于任意两块石头包括起点终点之间的间隔时必然不可行。所以我们可以设置left 1,right L。为了确保完全覆盖有时会设置right L 1这样即使check(L)为真我们的二分区间也能容纳它。在我的实践中更推荐一种清晰且不易出错的方式int left 1; // 最短跳跃距离至少为1 int right L; // 最长不会超过河的长度 // 或者考虑到如果所有石头都移走最短距离就是L所以rightL是合理的。3.2 二分循环的“左闭右开”与“左开右闭”抉择这是二分查找最容易写出死循环的地方。关键在于明确你维护的区间含义。我们寻找的是最后一个满足check(mid) true的D。假设我们维护的区间是[left, right]其中check(left)为真check(right)为假。我们的目标是不断缩小这个区间直到left和right相邻。我强烈推荐并使用“左闭右开”的写法即区间表示为[left, right)。它的循环不变式是left指向一个可行的答案right指向一个不可行或未探索的边界。最终当left 1 right时left就是我们要找的最大可行解。对应的循环模板如下while (left 1 right) { int mid left (right - left) / 2; // 防止溢出 if (check(mid)) { left mid; // mid可行说明答案至少是mid将左边界推进到mid } else { right mid; // mid不可行说明答案必须小于mid将右边界收缩到mid } } cout left endl; // 循环结束时left就是最大可行值这种写法的好处非常明显永不退循环条件left 1 right保证了区间内至少有两个元素时才需要循环。当区间缩小到[left, left1)时循环结束。更新清晰因为区间是右开的当mid可行时我们将left设为mid这很自然。当mid不可行时我们将right设为mid因为mid本身已经不可行新的右边界应该是它开区间不包含mid。答案明确循环结束后left就是最后一个被验证可行的值直接输出即可。对比常见的while (left right)写法那种写法需要处理mid的加减1并且最终答案的存储变量是left还是right还是ans容易混淆。“左闭右开”模板将答案的维护隐含在了区间边界里逻辑更简洁几乎可以成为二分答案问题的标准写法。3.3 一个完整的算法流程梳理读入L, N, M以及石头位置数组stones。为了方便处理可以在数组开头插入0起点末尾插入L终点。定义check(int d)函数实现上述贪心逻辑返回布尔值。初始化二分边界left 1,right L 1或right L但需确保check(L)为真时也能正确处理。执行“左闭右开”的二分循环。输出left。4. 代码实现、测试与极端情况分析理论清晰之后我们来落地成代码并思考一些边界情况确保我们的解决方案是健壮的。4.1 完整的C代码实现#include iostream #include vector #include algorithm using namespace std; int L, N, M; vectorint stones; // 判断是否能在移走不超过M块石头的情况下使得最短跳跃距离至少为d bool check(int d) { int last_pos 0; // 起点位置 int removed 0; // 遍历所有石头 for (int i 0; i N; i) { if (stones[i] - last_pos d) { // 距离太近必须移走当前石头 removed; if (removed M) { // 移走数量已超限提前返回false return false; } } else { // 可以跳过去更新上一个位置 last_pos stones[i]; } } // 检查最后一块保留的石头到终点的距离 // 注意终点L已经包含在stones数组末尾了吗这里假设没有。 // 更稳妥的做法是将终点L也视为一块“石头”加入数组这样循环内就包含了终点判断。 // 以下是未将终点加入数组时的判断 if (L - last_pos d) { return false; // 最后一段跳不到终点 } return removed M; } int main() { cin L N M; stones.resize(N); for (int i 0; i N; i) { cin stones[i]; } // 为了方便可以对石头位置排序题目虽说是升序给出但排序是个好习惯 sort(stones.begin(), stones.end()); // 二分查找 int left 1; int right L 1; // 右开区间L1是一个肯定不可行的值因为最大距离是L while (left 1 right) { int mid left (right - left) / 2; if (check(mid)) { left mid; // mid可行尝试更大的 } else { right mid; // mid不可行缩小范围 } } cout left endl; return 0; }代码优化点如注释所述将终点L作为一块“石头”插入stones数组末尾可以使check函数逻辑更统一无需单独判断最后一段。修改如下stones.push_back(L); // 在输入并排序后加入终点 N stones.size(); // 更新石头数量包含了终点 // 修改check函数移除对 L - last_pos 的单独判断因为终点已在数组中。 bool check(int d) { int last_pos 0; int removed 0; for (int pos : stones) { // 现在stones包含了终点 if (pos - last_pos d) { removed; if (removed M) return false; } else { last_pos pos; } } return true; // 如果能遍历完所有“石头”包括终点说明成功到达 }4.2 极端情况与测试用例任何健壮的算法都需要考虑边界。情况一M 0一块石头都不能移。此时问题退化为给定间隔求最小间隔的最大值实际上答案就是所有相邻石头包括起点终点间隔的最小值。我们的算法能工作吗可以。check(D)函数会尝试移走距离小于D的石头但因为M0一旦需要移走就会返回false。二分会找到最大的那个D使得没有任何间隔小于D即所有间隔都 D。这个D就是最小间隔。情况二M N所有石头都可以移走。此时我们可以移走所有石头直接从起点跳到终点。那么最大的最短跳跃距离就是河的长度L。我们的算法中check(L)会成功吗在贪心过程中因为起点0到任何一块石头的距离都小于L除非石头就在L所以所有石头都会被标记为移走removed N满足removed M。并且最后last_pos还是0终点L到0的距离等于L满足条件。所以check(L)返回true。二分会找到L。情况三石头位置有重复。题目通常保证位置互异但如果输入有重复我们的算法依然有效。对于两个位置相同的石头它们之间的距离为0在任何D0的情况下第一块都会被保留第二块会被移走因为距离0 D。情况四L很小N很大。二分查找的复杂度是 O(logL * N)在常规数据范围内L10^9, N50000完全可行。4.3 与“最小值最大化”同类问题的对比“河中跳房子”是“最小值最大化”问题的典型代表。类似的还有“进击的奶牛”在一条数轴上放N个牛棚要放入C头牛使得任意两头牛之间的最小距离最大。解法几乎一模一样check(d)函数判断能否在保证牛之间距离至少为d的情况下放下所有牛。“砍树”有N棵树需要砍下M米长的木材锯子的高度为H树木高于H的部分会被砍下。求最大的H使得砍下的木材总长度至少为M。这里check(H)计算木材总长度是否 M。“分配预算”将总额为M的预算分配给N个项目每个项目有一个最低需求和最高需求求在满足所有项目最低需求后能使获得预算最少的那个项目得到的预算最大值。check(x)判断能否在满足每个项目至少获得x预算的前提下分配完总预算。它们的共同模式是答案是一个数值其可行性与数值大小呈单调关系通常数值越大越难满足条件并且存在一个判断给定数值是否可行的函数。识别出这种模式就立刻可以套用二分答案的框架。5. 从二分答案到更广阔的算法思维通过“河中跳房子”这个具体的例子我们深入演练了二分答案的完整流程。但这道题的价值不止于此它更像一个引子让我们看到算法思维是如何层层递进的。5.1 贪心与二分的结合112这道题的精妙之处在于它将贪心和二分完美结合。贪心算法负责在给定约束下的快速可行性判断check函数其时间复杂度是O(N)。二分查找则负责在巨大的答案空间1到L中进行高效搜索时间复杂度是O(logL)。两者结合总复杂度为O(N logL)轻松处理大规模数据。这种“二分外壳 贪心/其他算法内核”的结构是解决许多最优化问题的标准套路。关键在于你必须能够写出一个正确的、单调的check函数。5.2 调试二分当答案不对时怎么办二分查找的bug往往难以察觉。如果你得到的答案不对可以按以下步骤排查验证check函数这是最容易出错的地方。构造几个小例子手动模拟check(D)的过程特别是边界情况D很小、D很大、M0、MN。确保你的贪心逻辑是正确的。验证二分边界打印出循环过程中left,right,mid和check(mid)的值。观察区间是否在正确收敛。确保你的初始right设置得足够大是一个肯定不可行的值。验证循环条件确认你的循环最终会停止。对于“左闭右开”模板while (left 1 right)是安全的。验证最终答案循环结束后输出的是left还是right根据你的区间定义来确认。在我们的模板里输出left。5.3 举一反三识别二分答案的适用场景在以后的刷题或工作中如何判断一个问题是否能用二分答案解决问自己三个问题问题的答案是一个数值吗通常是最大或最小的某个指标。如果我猜一个答案我能相对容易地判断它是否“可行”吗即能写出check函数。可行性和数值大小之间是否存在单调性例如对于“最小值最大化”问题数值越大越难满足对于“最大值最小化”问题数值越小越难满足。如果这三个问题的答案都是“是”那么二分答案就很可能是一个高效的解决方案。它把求解最优值的问题转化为了若干个判定性问题极大地简化了思维难度。回过头看“1247河中跳房子”它之所以经典就是因为它干净利落地呈现了这个思维范式。没有多余的干扰直指核心。吃透这道题你收获的不仅仅是一个AC的代码更是一种面对复杂最优化问题时化繁为简、分而治之的强大武器。下次再遇到“最大的最小”、“最小的最大”这类字眼你会条件反射般地想到也许可以试试二分答案。