如果你最近在准备一线大厂的OD机考大概率在C卷题库里刷到过一道叫“最佳植树距离”的题。光看题名你会以为它考的是贪心排序真正动手写才发现它考察的是二分答案和贪心检验的配合而且这个配合很容易在细节上翻车。我见过不少同学样例跑通、一提交就红也见过有人用暴力搜排列在本地等了两分钟还没出结果。今天这篇文章就把这道题彻底拆开题面怎么读、模型怎么转化、check函数为什么这样写、五种语言下有哪些隐蔽的坑全部一次说清。无论你是冲刺OD机考的考生还是想补二分答案这块短板的算法学习者这篇都值得收藏。1. 题目到底在考什么把“种树”翻译成算法模型1.1 题面还原输入、输出与最常考的样例先说清楚题面因为这道题的描述在考试里经常被包装得很绕。按我遇到最频繁的版本还原题目大意是这样的有一条笔直的道路道路上有N个可用的植树坑位给出每个坑位的坐标。现在需要从这N个坑位中选出K个位置来种树要求任意两棵相邻的已种树之间的距离都尽量大。换句话说这K棵树把所有可用位置分成若干段我们要让这些段里最短的那一段尽可能长。典型的输入格式是5 1 2 4 8 9 3第一行是坑位数量N第二行是N个整数坐标第三行是要种的树的数量K。上面例子的输出是3为什么是 3我们看看几种选法选坐标1、4、8相邻距离是3、4最小距离是3选坐标1、4、9相邻距离是3、5最小距离还是3选坐标1、8、9相邻距离是7、1最小距离只有1所以不管怎么选能保证的最小距离最大只能到 3。题目要你输出的就是这个最大可能值。这个题在机考里通常被归为“中等题”原因是它不像排序题那样一眼看到解法需要你主动意识到“最大化最小值”这个关键词然后想到二分答案这条路。1.2 核心瓶颈不要被“平均距离”带偏我第一次做这道题的时候第一反应是把所有坑位排序然后用总长度除以K - 1得到一个大致的“平均间距”再微调一下。这个思路错得很离谱。举个反例4 1 2 100 101 2如果按平均间距的思路全长是 100要种 2 棵树平均距离也是 100看起来答案好像是 100。实际上你只需要选1和101两个位置距离就是 100所以答案确实是 100。这个例子还不够有说服力换个例子5 1 2 100 101 200 3平均间距是 199 / 2 99.5取整后大概是 99。但最优选择是1、101、200相邻距离是 100 和 99最小距离是 99或者选1、100、200最小距离也是 99。好像跟平均间距差不多。再换一个不均匀的5 1 50 51 52 100 3平均间距是 49.5但如果你选1、50、100最小距离是 49选1、52、100最小距离是 48。看起来还是要动态判断不能简单平均。真正的问题在于我们要的不是“平均尽量大”而是“最差的那一段尽量大”。这就像组队比赛不是看全队平均实力而是看最弱的那个队员有多强。平均法完全无视了最弱环节所以会错。1.3 为什么暴力枚举不现实既然平均法不行那能不能暴力枚举所有组合假设N 100000K 50000选 5 万个位置的组合数是个天文数字现代计算机跑一年也跑不完。所以必须换个思路。观察一下“最大化最小值”这类问题它有一个很好的性质决策空间是连续线性的而且可行性随答案单调变化。这个性质是二分答案的敲门砖。如果某个间距d能种下至少K棵树那么任何比d小的间距也一定能种下至少K棵树因为条件更宽松了反过来如果某个间距d种不下K棵树那么任何比d大的间距也种不下。这就是单调性有单调性就能二分。2. 为什么非要用二分答案单调性与check函数的证明2.1 单调性距离越大能种下的树越少二分答案的本质是我们不去直接求最终的间距而是猜测一个间距d然后问自己一个问题——“如果要求任意两棵相邻树之间的距离都至少是d我能种下至少K棵树吗”这个问题的答案随d的变化规律很清楚d 0时所有坑位都能种树肯定能种下至少K棵。d慢慢变大能种下的树就会变少。d大到超过整条道路长度时最多只能种 1 棵树大概率种不下K棵。用生活里的例子类比想象一场考试及格线定得越低通过的人越多及格线定得越高通过的人越少。“及格线”就是这里的间距d“通过人数”就是能种下的树的数量。我们要找的是“刚好还能让至少K个人通过的最高及格线”。这个单调关系保证了对间距做二分一定是安全的因为整个判断函数长这样对于小的d判断结果为真对于大的d判断结果为假。中间必然存在一个分界点这个分界点就是我们要求的答案。2.2 check函数的设计与贪心证明既然要对d做判断就必须写一个函数can(d)。这个函数是所有实现里最核心的部分。我的写法是这样的第一个坑位必种记为 last a[0] 从第二个坑位开始遍历 如果当前坑位 a[i] 与 last 的距离 d 就在 a[i] 种一棵树 last a[i] 已种数量 cnt 遍历完所有坑位后如果 cnt K返回 true为什么第一个坑位必种这里有个贪心策略。假如存在某个最优方案第一棵树种在a[j]而不是最左边的a[0]那么我把第一棵树挪到a[0]由于a[0]在a[j]的左边后续所有坑位与上一棵树的距离只会变大不会变小所以后续能选的坑位集合至少不会变差。也就是说第一棵树种在最左边一定不亏。同理在遍历过程中如果当前位置a[i]满足条件与上一棵树的距离大于等于d在当前方案里种下这棵树也不亏。有人可能会想万一我不种这棵把机会留给后面会不会更好不会。因为不种a[i]而改种后面的a[j]只会让last变大从而让下一个坑位更难满足距离约束。既然现在就能种种下去就是最优选择。这就是“能种就种”的贪心策略。它不需要回溯不需要动态规划因为它处理的是一个一维线性问题局部最优可以直接推出全局最优。这个证明在面试或者复盘时很值得写下来因为很多人会问“为什么贪心是对的”。2.3 边界处理整数二分模板与防死循环技巧下面是二分骨架几乎可以套在所有“最大化最小值”题目里l 0 r a[N-1] - a[0] while l r: mid (l r 1) / 2 if can(mid): l mid else: r mid - 1 输出 l这里有两个非常关键的点。第一mid要取(l r 1) / 2上取整不能取(l r) / 2。因为当can(mid)为真时答案是“至少 mid”我们要让左边界继续向右逼近当can(mid)为假时答案是“最多 mid - 1”右边界向左缩。如果mid取下取整在l 1, r 2时会算出mid 1如果can(1)为真l还是 1这就死循环了。上取整能保证区间每次都严格缩小。第二右边界r的理论最大值是“整条道路的总跨度”也就是a[N-1] - a[0]。更紧一点可以写成(a[N-1] - a[0]) / (K - 1)因为要种K棵树相邻间距再大也不可能超过总跨度除以K-1段。这个优化能让二分次数少十几轮不过代码可读性稍微差一点实际考试里用总跨度做右边界完全够。整个算法的时间复杂度是O(N log R)R是坐标跨度的范围排序另外占O(N log N)。机考的数据量一般到 10 万级别这套做法轻松跑进 1 秒。3. 五种语言完整实现与各自的坑这一节给出 Java、Python、JavaScript、C、Go 五种语言的完整代码。我尽量保持逻辑一致并标出每种语言最隐蔽的坑。机考真正扣分的地方往往不是算法本身而是这些语言层面的细节。3.1 Java 实现类名和 long 是关键import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] a new int[n]; for (int i 0; i n; i) { a[i] sc.nextInt(); } int k sc.nextInt(); Arrays.sort(a); long l 0; long r a[n - 1] - a[0]; while (l r) { long mid (l r 1) / 2; if (can(a, k, mid)) { l mid; } else { r mid - 1; } } System.out.println(l); } static boolean can(int[] a, int k, long d) { int cnt 1; int last a[0]; for (int i 1; i a.length; i) { if (a[i] - last d) { cnt; last a[i]; if (cnt k) return true; } } return cnt k; } }Java 有两个点要注意一是类名必须叫Main否则机考平台可能报错二是二分区间最好用long。虽然这道题坐标差通常还在int范围内但万一坐标范围给到10^9l r可能会接近2 * 10^9再算mid在 32 位int里就非常危险。用long可以彻底避开这个隐患。3.2 Python 实现统一用 sys.stdin.read() 读取import sys def solve(): data list(map(int, sys.stdin.read().split())) n data[0] a data[1:1 n] k data[1 n] a.sort() def can(d): cnt 1 last a[0] for x in a[1:]: if x - last d: cnt 1 last x if cnt k: return True return cnt k l, r 0, a[-1] - a[0] while l r: mid (l r 1) // 2 if can(mid): l mid else: r mid - 1 print(l) if __name__ __main__: solve()Python 最容易踩的坑是用input()逐行读。机考的输入数据有时会把所有数字放在同一行有时又分成多行还有可能在末尾多一个换行。sys.stdin.read().split()是万能解法一次把标准输入里的所有内容按空白字符切分再映射成整数。稳、快、兼容各种格式。另外Python 的闭包在can里直接引用了外层变量a、k这没问题。如果你非要在can里重新赋值cnt记得它只是局部变量不需要声明nonlocal因为cnt从头到尾都是局部变量。3.3 JavaScript 实现sort 默认排序是大坑const readline require(readline); const rl readline.createInterface({ input: process.stdin }); const lines []; rl.on(line, (line) { lines.push(line.trim()); }); rl.on(close, () { const data lines.join( ).split(/\s/).map(Number); const n data[0]; const a data.slice(1, 1 n); const k data[1 n]; a.sort((x, y) x - y); function can(d) { let cnt 1; let last a[0]; for (let i 1; i a.length; i) { if (a[i] - last d) { cnt; last a[i]; if (cnt k) return true; } } return cnt k; } let l 0; let r a[a.length - 1] - a[0]; while (l r) { const mid (l r 1) 1; if (can(mid)) { l mid; } else { r mid - 1; } } console.log(l); });Node.js 环境里readline是标准的读入方式。两个坑很典型第一个是sort()默认按字符串顺序排列[1, 2, 10]会被排成[1, 10, 2]所以必须传(x, y) x - y。第二个是 1只对 32 位整数安全如果坐标差特别大建议用Math.floor((l r 1) / 2)。这道题正常范围内 1没问题但保守一点写Math.floor(...)更稳。3.4 C 实现lambda 捕获和 long long#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } int k; cin k; sort(a.begin(), a.end()); auto can [](long long d) - bool { int cnt 1; int last a[0]; for (int i 1; i n; i) { if (a[i] - last d) { cnt; last a[i]; if (cnt k) return true; } } return cnt k; }; long long l 0; long long r a[n - 1] - a[0]; while (l r) { long long mid (l r 1) / 2; if (can(mid)) { l mid; } else { r mid - 1; } } cout l \n; return 0; }C 里cin在数据量达到十万级别时其实不会成为瓶颈但加上ios::sync_with_stdio(false)和cin.tie(nullptr)是考试时的好习惯能避免一些隐性的性能损耗。auto can [](long long d) - bool这种 lambda 写法可以捕获外部的a、n、k非常方便。要注意 lambda 的返回类型如果你不写- bool编译器有时会猜测成int或别的类型显式写清楚更安全。如果你不喜欢 lambda也可以单独写一个函数把数组、n、k全传进去。不过我个人觉得 lambda 在闭包场景下更直观代码也更短。3.5 Go 实现ScanWords 解决多行读取package main import ( bufio fmt os sort strconv ) func main() { scanner : bufio.NewScanner(os.Stdin) scanner.Split(bufio.ScanWords) read : func() int { scanner.Scan() v, _ : strconv.Atoi(scanner.Text()) return v } n : read() a : make([]int, n) for i : 0; i n; i { a[i] read() } k : read() sort.Ints(a) can : func(d int) bool { cnt : 1 last : a[0] for i : 1; i n; i { if a[i]-last d { cnt last a[i] if cnt k { return true } } } return cnt k } l, r : 0, a[n-1]-a[0] for l r { mid : (l r 1) / 2 if can(mid) { l mid } else { r mid - 1 } } fmt.Println(l) }Go 读入数据常见的坑是bufio.Scanner默认按行切分。如果坐标都挤在同一行那没问题如果坐标跨了多行按行读就很痛苦。所以我在一开始就调用了scanner.Split(bufio.ScanWords)让扫描器按单词切分不管换行还是空格都能正确读进来。read这个闭包函数把“读一个整数”这件事封装起来代码看起来干净用起来也顺手。int在 64 位平台上是 64 位所以这道题不需要额外用int64。如果你在 32 位平台写 Go那才需要考虑溢出问题机考一般不用管这个。4. 双机位机考环境下的实战策略与自测清单4.1 提交前一定要做的一组自测双机位监考意味着你没有太多机会反复试错切屏还可能被记录。所以提交之前最好在脑子里过一遍这组测试用例能帮你拦下大部分低级错误。测试场景输入示例期望输出检查点普通乱序5/9 1 4 8 2/33排序是否生效只种两棵树4/1 2 100 101/2100贪心是否直接选首尾全部种满5/1 2 4 8 9/51KN 时取最小相邻差有重复坐标4/1 1 2 2/21重复点不干扰判断极度稀疏3/0 100 200/2200上界是否正确“全部种满”这个用例很多人会忽略。当K N时所有坑位都必须种树答案就是排序后相邻坐标差的最小值。二分答案在遇到这种情况时依然能正确算出来因为can(1)大概率成立can(2)不成立最终输出就是 1。如果你在本地跑这个用例发现输出不对说明你的can函数或边界条件有问题。4.2 双机位环境的临场细节双机位机考一般要求一台设备作为主答题机另一台设备从侧面拍摄答题过程。这意味着你的操作画面基本全程可见任何切屏、打开其他文档的操作都可能在监控记录里留下痕迹。所以考前我强烈建议做两件事第一把上面五种语言里你最熟悉的那一种的模板代码提前敲熟至少要熟到能盲打出来。考试时不需要临时回忆语法省下的时间全部用来分析题面。第二机考平台的在线编辑器和本地 IDE 可能有差异。在线编辑器通常没有智能补全缩进和自动格式化也不够友好。建议平时练习时就只用普通文本编辑器写代码这样考试时不会因为编辑器差异而手忙脚乱。第三标准输入输出是唯一可靠的方式。不要在代码里写死任何文件路径也不要依赖 IDE 的运行按钮养成用命令行java Main、python3 main.py、node main.js运行的习惯能提前暴露很多环境问题。4.3 举一反三怎么一眼认出“二分答案题”“最佳植树距离”不是孤例它属于一大类题目识别信号非常明显题目里出现“最大化最小值”“最小化最大值”“至少达到多少”“最远距离尽可能小”这类描述答案是一个整数而且范围很大如果直接枚举答案复杂度很高如果直接贪心你又说不清贪心依据一旦识别出来就套用“二分答案 check 函数”的框架。关键是 check 函数要切题这道题是“按距离选位置”换成数组分段题就是“按区间和选段数”换成雷达覆盖题就是“按覆盖范围选雷达点”。模板是死的check 是活的真正的区分度就在 check 的设计上。我这里提一个很常见的变体给你一个数组要求分割成M段使得“所有段的和的最大值”最小。这也是二分答案check 变成贪心累加超过猜的值就开新段。如果你能把“最佳植树距离”的 check 思路迁移到那个题上说明你真的把二分答案吃透了。5. 最容易翻车的四个边界细节5.1 坐标默认有序是大忌很多同学看到1 2 4 8 9这种样例就以为输入一定有序直接跳过sort。机考评测数据几乎不会给你这种优待坐标可能是乱序的也可能有重复。不排序的话check 函数在遍历到前半段时会把last设成一个中间值后半段再遇到更大的坐标时判断逻辑就会乱掉。排序这个动作虽然只有一行但它的作用和必要性要刻在脑子里。5.2 K1 时的意义问题严格来说K 1时只种一棵树不存在“相邻两棵树”最小距离这个定义就失效了。大部分题目会保证K 2但为了稳妥可以在代码开头加一个特判if K 1: print(0) return输出 0 是题面里比较通用的约定表示没有相邻距离。如果原题没有这个约定你只需要根据题意调整即可。这个特判不会干扰主逻辑多写一行没坏处。5.3 二分终点为什么有人输出比答案小 1最典型的病根就是mid (l r) / 2。前面 2.3 里说过下取整配合l mid会造成死循环。如果你没死循环而是输出比正确答案小 1通常是为了避免死循环把l mid写成了l mid 1。这个改动看起来是常识因为真了就前进但在“最大化最小值”这种模板里是错误的因为mid本身可能是有效答案1 会跳过它。正确区分两种模板最大化最小值本题if can(mid): l mid else r mid - 1最小化最大值if can(mid): r mid else l mid 1两套模板不可混用建议每种都敲一遍形成肌肉记忆。5.4 右边界写死 1e9 的问题有人图省事直接r 1000000000。这样对答案基本不会产生错误只是多跑几次二分性能损失十几轮通常不至于超时。但如果坐标范围本来就很小比如0 到 10你却把上界写死成1e9二分区间从 10 变成 1e9白白多了将近 30 轮循环在时间紧张的机考里是没有必要的。最稳妥的方式是r a[N-1] - a[0]既符合逻辑又不会浪费性能。更苛刻的优化是除以K - 1不过那是锦上添花不是必须。5.5 不同语言读入方式的差异这一节其实在第三章已经详细说过这里再总结成一句话Java 用ScannerPython 用sys.stdin.read()JS 用readline按行收集再合并C 用cin并开启同步关闭Go 用ScanWords。背下自己语言的读入模板比现场调试快得多。6. 复盘模板怎么记忆才不容易忘这道题做多了以后我的体会是代码本身不值钱值钱的是把“最大化最小值”和“贪心 check”之间的连接想通。你如果只背模板过两周一定会忘如果你在草稿纸上画一条数轴模拟一遍can(3)在1 2 4 8 9上的执行过程你就能理解为什么第一个必须种、为什么能种就种、为什么右边界可以取总跨度这些东西比任何模板都牢固。考试时如果卡在 check 函数上我的建议是先写一个非常幼稚的版本遍历所有位置能种就种不管性能。跑样例验证逻辑方向对不对。然后再考虑用排序、二分去优化。这个“先写对再写快”的顺序能帮你避免在考场上陷入“明明思路对但细节全错”的泥潭。关于这道题的时间分配我个人的经验是读题 5 分钟模型转化 10 分钟写代码 10 分钟反复自测 10 分钟。如果超过 35 分钟还没完全跑通先停下来检查题目是不是读歪了再检查边界实在不行就先把当前版本提交一个最暴力的写法保底不要跟一个细节死磕到底。最后再分享一个小技巧所有二分答案的题都可以用“三组自测”来验证模板——最小区间、最大区间、K 等于 N。三组全过这道题基本就稳了。看到“最小距离最大化”就条件反射地二分但真正的胜负手永远是那个 check 函数——希望这篇能把它的来龙去脉讲透帮你少走我当年走过的弯路。