二分答案算法精讲：从河中跳房子问题理解最大化最小距离

1. 项目概述从“河中跳房子”到二分答案的思维跃迁“河中跳房子”这个听起来有点童趣的名字其实是算法竞赛和编程练习中一道非常经典的二分答案例题在不少在线评测系统如POJ, USACO里的题号就是1247。我第一次遇到这道题时感觉它完美地诠释了“二分”这个思想不仅仅是用来在有序数组里找某个数那么简单。它更像是一把万能钥匙当一个问题满足“答案具有单调性”且“验证答案是否可行相对容易”这两个条件时二分答案就能大显身手。这道题就是训练我们识别这种问题模式并将抽象的二分思想转化为具体代码的绝佳素材。简单来说题目是这样的有一条笔直的河河中间有N个石头房子它们距离起点的位置已知。现在我们要从起点跳到终点每次跳跃至少需要跳过M个石头即移除一些石头使得剩下的石头中相邻两块之间的距离都不小于某个值D。我们的任务是给定最多可以移除的石块数量求这个最短跳跃距离D的最大可能值。这听起来有点绕但核心就是我们想找到那个最大的D使得在移除不超过给定数量的石头后所有剩余石头间的距离都至少是D。这个D就是我们二分的对象。无论你是正在备战算法竞赛的学生还是希望深化对二分理解的在职开发者吃透这道题都能让你对“二分答案”这个强大工具的理解上一个台阶。2. 核心思路拆解为什么二分答案是正解2.1 问题重述与数学模型建立我们先把题目翻译成更严谨的表述。设河的长度为L起点坐标为0终点坐标为L。中间有N个石头其坐标保存在一个数组stones[N]中且stones[0] 0起点stones[N1] L终点。我们定义一个最短跳跃距离min_dist。现在如果规定每次跳跃距离不能小于min_dist那么有些石头可能就显得“太近”了。为了满足这个最小距离约束我们可以移除一些石头。题目会给定一个最多可以移除的石块数量M。我们的目标是找到一个最大的min_dist使得在移除不超过M块石头后从起点到终点依次经过剩余石头及起点终点时相邻两点间的距离都大于等于这个min_dist。这个min_dist就是我们要的答案。直接求解似乎无从下手因为min_dist的可能取值是一个连续的范围从0到L我们无法枚举所有可能。这时就要观察其性质。2.2 单调性分析二分可行性的基石二分答案能够应用的核心前提是单调性。在这道题中单调性体现在哪里让我们定义一个函数check(dist): 它判断是否能够通过移除不超过M块石头使得所有相邻石头间距都至少为dist。这个函数的返回值是布尔值True或False。关键来了如果某个距离dist是可行的即check(dist) True那么所有比dist小的距离也一定是可行的吗反过来如果dist不可行那么所有比dist大的距离呢我们来思考一下假设dist 5可行。这意味着我们能用不超过M次移除让间距都5。那么对于dist 4要求间距4这比5更宽松。既然在更严格的要求5下都能做到那么在更宽松的要求4下我们完全可以采用相同的移除策略甚至移除更少的石头来满足条件。所以如果dist可行那么所有比它小的dist都可行。假设dist 10不可行。这意味着我们无法通过移除M块石头来让所有间距10。那么对于dist 11要求间距11这比10更严格。在更宽松的要求下都做不到在更严格的要求下更不可能做到。所以如果dist不可行那么所有比它大的dist都不可行。这个性质完美符合二分查找所要求的“有序性”。我们可以把所有可能的dist想象成一个数轴在这个数轴上存在一个临界点X。所有dist X的点check(dist)都为True所有dist X的点check(dist)都为False。我们的目标就是找到这个最大的X。这正是二分查找的典型场景。2.3 方案对比为何不是动态规划或贪心看到“最大最小值”或“最小最大值”这类问题有经验的同学可能会想到动态规划DP。理论上这道题可以用DP来解定义状态dp[i][k]表示跳到第i个石头、已经移除了k块石头时上一跳的最小距离最大值。但这样状态复杂度是O(N*M)转移方程也比较复杂不仅实现难度大而且效率通常不如二分答案。贪心策略呢比如每次遇到距离小于当前尝试的dist的石头就移除这其实是check函数内部采用的策略但它不能直接用于求解最终的dist。因为贪心策略的正确性依赖于一个给定的dist值。我们需要二分来找到那个能让贪心策略恰好满足移除石头数量约束的、最大的dist。所以**“二分答案 贪心验证”**的组合才是这道题最简洁、最高效、最经典的解法。二分负责在答案空间0, L]内进行对数级别的搜索而贪心负责以O(N)的复杂度快速验证每一个猜测的答案是否可行。两者结合时间复杂度为O(N log L)在常规数据范围下非常高效。3. 贪心验证函数的详细实现二分框架是骨架而check函数是血肉。这个函数的设计直接决定了算法的正确性和效率。它的任务是对于给定的一个尝试答案mid即假设的最小跳跃距离判断是否可行。3.1 验证算法的核心逻辑验证算法采用一个模拟跳跃的贪心过程我们维护一个“上一块石头”的位置last_pos初始化为起点0。从第一块真正的石头stones[1]开始依次遍历到终点前的最后一块石头stones[N]。对于当前遍历到的石头stones[i]计算它到last_pos的距离gap stones[i] - last_pos。如果gap mid说明如果保留这块石头跳跃距离就小于我们尝试的mid不满足要求。因此这块石头必须被移除。移除计数remove_cnt加1。如果gap mid说明从last_pos跳到stones[i]是满足距离要求的。那么这块石头就可以作为新的起跳点。于是更新last_pos stones[i]继续检查下一块石头。遍历结束后我们还需要检查从最后的last_pos到终点L的距离是否也 mid。如果不满足说明整个路径无法达成但根据我们的贪心策略这种情况实际上在遍历中就会导致无法抵达通常check函数直接返回False。更稳妥的做法是在遍历结束后也判断一下L - last_pos mid。最后判断移除的石块数量remove_cnt是否 M。如果是则说明对于这个mid存在一种移除方案就是我们贪心模拟的这种方案使得条件满足函数返回True否则返回False。注意这里有一个非常重要的细节也是容易出错的地方。终点L是必须到达的不能移除。我们的贪心策略保证了在移除石头后剩下的石头序列加上终点其相邻距离是满足mid的。但有一种边界情况如果最后一块保留的石头距离终点太近L - last_pos mid而我们又无法再移除终点了那么这个mid就是不可行的。我们的算法在遍历中当last_pos被更新到最后一块保留的石头时就已经固定了所以必须在最后检查这一步。3.2 代码实现与逐行解析下面以C为例展示check函数的一种清晰实现bool check(long long mid, vectorlong long stones, int L, int M) { int remove_cnt 0; // 移除石头计数器 long long last_pos 0; // 上一个保留的位置初始为起点0 int n stones.size(); // 石头数量包含起点和终点吗这里假设stones[0]0, stones[n-1]L // 遍历从第1块到第n-2块石头跳过起点和终点 for (int i 1; i n - 1; i) { if (stones[i] - last_pos mid) { // 距离太近必须移除当前石头 remove_cnt; if (remove_cnt M) { // 如果移除数量已经超过限额提前返回失败 return false; } } else { // 距离足够保留当前石头并更新上一个位置 last_pos stones[i]; } } // 检查最后一段从最后一个保留的位置到终点的距离 if (L - last_pos mid) { return false; } // 最终判断移除数量是否在允许范围内 return remove_cnt M; }关键点解析参数与类型mid和坐标可能很大使用long long避免溢出。stones数组包含了所有石头坐标包括起点和终点。循环范围for (int i 1; i n - 1; i)确保我们只遍历中间的石头不处理起点(0)和终点(L)因为它们不可移除。提前剪枝if (remove_cnt M) return false;这是一个重要的优化。一旦在模拟过程中移除数量已经超标就可以立刻断定这个mid不可行无需继续模拟。最后一段检查if (L - last_pos mid) return false;这是保证路径完整性的关键。确保了从最后一个落脚点到终点的最后一跳也是合法的。3.3 贪心策略的正确性证明为什么这个简单的贪心策略遇到距离不够就移除当前石头是正确的我们需要证明按照这个策略得到的移除数量是在满足“所有跳跃距离mid”条件下移除石头数量最少的一种方案或者至少不差于最优方案。反证法思路假设对于某个mid存在一个最优移除方案其移除数量为kk M。现在我们按照贪心策略模拟得到了一个移除序列数量为g。如果贪心不是最优的那么可能存在g k。考虑第一个产生分歧的点。假设在遍历到第i块石头时最优方案选择保留它而贪心方案因为stones[i] - last_pos_greedy mid而移除了它。这意味着在贪心策略中last_pos_greedy上一个保留点的位置不晚于最优方案中的上一个保留点last_pos_opt因为贪心是见够就留保留点只会更靠前或相同。因此stones[i] - last_pos_greedy stones[i] - last_pos_opt。但贪心却判定距离不够这说明在最优方案中从last_pos_opt到stones[i]的距离也必然小于mid。否则如果最优方案中这个距离mid那么贪心策略中的last_pos_greedy更靠前距离只会更大贪心就不会移除它。因此最优方案中从last_pos_opt到stones[i]的距离也小于mid。但最优方案却保留了stones[i]这只能说明在最优方案中last_pos_opt之后、stones[i]之前的一些石头被移除了使得last_pos_opt的位置比贪心策略中的last_pos_greedy更靠后。然而贪心策略是遇到不够mid的才移除它保留石头的策略是尽可能早地确立新的起跳点。如果最优方案通过移除中间石头来“跳过”stones[i]那么贪心策略在遇到那些中间石头时如果距离够它就会保留并更新位置从而可能避免移除stones[i]如果距离不够它就会移除它们这和最优方案的做法在效果上是一致的。通过更细致的分析可以论证贪心策略得到的移除集合不会比任何最优方案差。它本质上是在维护一个“在当前mid要求下尽可能紧凑的合法路径”。因此用贪心策略计算出的最小移除数量来验证mid的可行性是正确的。4. 二分查找框架的构建与细节处理有了可靠的check函数二分查找的部分就相对模式化了。但其中仍有不少细节决定了代码的健壮性和效率。4.1 二分边界与循环条件我们要搜索的答案min_dist的范围是多少显然最小可能是0如果允许移除所有石头最大可能是河的长度L如果一块石头都不移除那么最小跳跃距离最大就是起点到终点的距离但通常答案会比L小。所以初始搜索区间可以设为[0, L]或(0, L]。由于距离必须是正数且0显然总是可行的check(0)一定为True我们可以将左边界设为1右边界设为L搜索区间为[1, L]。二分查找有两种常见的写法一种是维护区间[left, right]循环条件为left right另一种是维护区间[left, right)循环条件为left right。对于整数二分查找最大值的问题我推荐使用第二种因为它能更清晰地处理边界避免死循环。long long left 1; long long right L; // 注意右边界是L这是一个可行的最大值吗check(L)通常为False除非只有起点终点。 // 更稳妥的右边界是L但我们可以根据题意放宽或者直接使用一个很大的数如1e91。 right L 1; // 将右边界设为开区间确保答案在[left, right)内 while (left right) { long long mid left (right - left 1) / 2; // 偏右取整用于寻找最大可行值 if (check(mid, stones, L, M)) { // mid可行说明答案至少是mid也可能更大。搜索区间向右收缩 left mid; } else { // mid不可行答案必须比mid小。搜索区间向左收缩 right mid - 1; } } // 循环结束时left right即为所求的最大可行min_dist cout left endl;为什么mid要偏右取整当区间长度为偶数时(leftright)/2是向下取整。在寻找最大可行值的场景下如果check(mid)为真我们将left更新为mid。如果此时mid恰好是向下取整得到的且left和right相差1例如left3, right4那么mid (34)/2 3。如果check(3)为真则更新left3区间变为[3,4)left仍然小于right循环继续。但此时mid再次计算为(34)/23check(3)为真left又被更新为3……这就陷入了死循环。 将mid计算为left (right - left 1) / 2可以保证是向上取整。在上例中mid 3 (4-31)/2 4。如果check(4)为假则right 4-13循环结束如果为真则left4循环也结束。这样就避免了死循环。4.2 数据预处理与输入格式题目输入通常格式是第一行三个整数 L, N, M分别表示河的长度、中间石头数、最多可移除石头数。接下来N行每行一个整数表示石头距离起点的距离。 我们需要将这些石头坐标存起来并且为了方便处理把起点(0)和终点(L)也作为“石头”加入数组。然后对整个数组进行排序。因为题目不保证输入石头坐标是有序的。#include iostream #include vector #include algorithm using namespace std; int main() { int L, N, M; cin L N M; vectorlong long stones; stones.push_back(0); // 加入起点 for (int i 0; i N; i) { long long pos; cin pos; stones.push_back(pos); } stones.push_back(L); // 加入终点 sort(stones.begin(), stones.end()); // 排序 // ... 二分查找逻辑 }为什么要排序因为我们的贪心验证算法需要依次遍历石头计算相邻距离。如果石头坐标无序那么“相邻”的概念就乱了算法会得到错误的结果。排序保证了我们遍历的是河道上从左到右的石头序列。4.3 整合代码与复杂度分析将以上所有部分整合就得到了完整的解决方案#include iostream #include vector #include algorithm using namespace std; bool check(long long mid, vectorlong long stones, int L, int M) { long long last_pos stones[0]; // 起点 int remove_cnt 0; for (int i 1; i stones.size() - 1; i) { // 不处理终点 if (stones[i] - last_pos mid) { remove_cnt; if (remove_cnt M) return false; } else { last_pos stones[i]; } } // 检查最后一段最后一个保留点到终点的距离 if (stones.back() - last_pos mid) return false; return remove_cnt M; } int main() { int L, N, M; cin L N M; vectorlong long stones; stones.push_back(0); for (int i 0; i N; i) { long long pos; cin pos; stones.push_back(pos); } stones.push_back(L); sort(stones.begin(), stones.end()); long long left 1; long long right L 1; // 开区间 while (left right) { long long mid left (right - left 1) / 2; if (check(mid, stones, L, M)) { left mid; } else { right mid - 1; } } cout left endl; return 0; }时间复杂度分析排序O(N log N)其中N是石头数量。二分查找循环次数为 O(log L)因为搜索范围是河长L。每次check需要遍历一次石头数组O(N)。总时间复杂度O(N log N N log L)。通常N log N项占主导但对于L很大而N适中的情况N log L是主要部分。这个复杂度对于N, L在10^5量级的问题是完全可以接受的。空间复杂度O(N)用于存储石头坐标。5. 常见陷阱、调试技巧与扩展思考5.1 实战中容易踩的坑整数溢出这是最隐蔽的坑。河长L、石头坐标、距离mid都可能达到10^9级别。在计算距离stones[i] - last_pos特别是二分计算mid (left right) / 2时leftright可能会超过32位整型(int)的范围导致溢出变成负数进而引发一系列错误。务必使用long long64位整型来存储所有与坐标、距离相关的变量。二分边界与死循环如前所述在寻找最大值时使用mid left (right - left) / 2向下取整并更新left mid在特定情况下会导致死循环。必须使用mid left (right - left 1) / 2向上取整。相反如果寻找最小值更新right mid时mid就应该向下取整。记住口诀更新左边界时中间值向上取整更新右边界时中间值向下取整。终点处理在check函数中很容易忘记检查最后一段从最后一个保留石头到终点的距离。如果漏掉可能会错误地判断某些mid为可行。一个简单的记忆方法是我们的目标是保证每一段跳跃都满足条件起点到第一块保留石头、保留石头之间、最后一块保留石头到终点这三部分都需要检查。循环中处理了前两部分循环后必须补上第三部分。输入石头包含起点终点有些题目输入可能已经包含了起点和终点有些则没有。我们的代码选择主动加入起点0和终点L并排序这样逻辑最清晰。如果输入已经包含则需要调整避免重复加入。M等于0或N的情况当不允许移除任何石头M0时答案就是所有相邻石头间距的最小值。当可以移除所有中间石头MN时答案就是河的长度L。我们的算法能正确处理这些边界情况吗可以。当M0时check函数一旦发现距离小于mid因为不能移除只能通过更新last_pos来尝试但如果更新后最后一段距离不够还是会返回false。二分会找到正确的最大mid即最小间距。当MN时check函数几乎总是返回true除非mid大于L二分会找到L。5.2 调试与验证方法当你觉得代码逻辑正确但提交总是Wrong Answer时可以尝试以下方法小数据手工模拟构造一个很小的例子比如L10石头在[2,4,7]M1。用手算一下答案应该是多少尝试移除不同的石头看最大最小距离是多少。然后用你的程序跑单步调试check函数和二分过程看中间结果是否和手算一致。打印调试信息在check函数中打印出传入的mid值以及每次决定移除或保留石头时的last_pos、当前石头位置、remove_cnt。观察贪心过程是否符合预期。验证单调性随机生成一组数据和M然后写一个暴力程序从小到大枚举所有可能的dist比如步长设为1调用你的check函数看返回值是否真的呈现True, True, ..., True, False, False, ...的模式。这可以验证你的check函数逻辑是否正确。二分区间检查确保你的二分初始区间足够大能覆盖所有可能答案。例如答案最大可能是L当所有中间石头都被移除所以右边界至少是L。保险起见可以设为L1开区间或一个很大的数如1e91。5.3 问题扩展与变种“河中跳房子”是“最小化最大值”问题的典范。掌握其思想后可以解决一大类问题Aggressive cows (POJ 2456)农夫有N个牛棚在一条线上要安排C头牛入住使得任意两头牛之间的最小距离最大。这几乎是同一道题把“石头”换成“牛棚”“移除石头”换成“选择牛棚入住”“最小跳跃距离”换成“牛之间的最小距离”。Pie (POJ 3122)有N个派要分给F1个人每个人分到的派必须来自同一个派且体积一样求每个人能分到的最大体积。这里“体积”就是我们要二分的答案check函数是判断能否用这些派切出至少F1份指定体积的派。木材加工 (洛谷 P2440)有N根木头需要切割出至少K段等长的小木头求小木头的最大长度。二分长度check函数计算每根木头能切出多少段。这些问题的共同点是答案是一个数值并且我们可以很容易地判断一个给定的答案是否“可行”或“过严/过松”。一旦识别出这个模式二分答案就是首选的解题框架。最后我个人在刷这类题目时的体会是二分答案的难点往往不在于二分查找本身而在于如何设计出正确且高效的check函数。check函数的设计需要你对问题有深刻的理解有时需要一点贪心有时需要一点动态规划。多练习几道变种题就能培养出快速识别问题和设计验证函数的能力。这道“河中跳房子”就是一个完美的起点它清晰地展示了从问题抽象、单调性证明、验证函数设计到二分实现的完整思维链条。