最近不少同学在准备华为OD机考C卷里有一道“最佳植树距离”反复出现而且网上讨论热度一直很高。我第一次看到这题时下意识想用暴力枚举去解样例倒是过了一到真实数据直接超时后来才反应过来这是典型的“二分答案 贪心校验”套路。这篇文章把我自己踩过的坑、五种种语言Java、Python、JS、C/C、Go的完整实现以及机考双机位现场的注意事项一起整理出来。无论是正在冲刺华为OD机试还是单纯想练二分查找这道经典题都可以直接拿这篇去对照复习。1. 先把题意吃透最佳植树距离到底在求什么1.1 题目场景还原题目本身描述得非常生活化你有一排坑位每个坑位在数轴上有一个固定的坐标位置现在要在这些坑位里选若干位置种树而且要求种下去的树之间“不能太挤”——任意两棵树之间的直线距离都必须不小于某个值D。问题问的是在满足“刚好能种下M棵树”的条件下这个最小距离D最大能取多少。举个最简单的例子坑位坐标是 [1, 2, 8, 9]总共4个坑要在其中选2个坑种树。如果选1和9两树距离是8这是能取到的最大最小距离吗没错就是8。那如果要在4个坑里种3棵树结果就不是8了因为选1、8、9的话8和9之间距离只有1刚刚说过任意两棵树之间的距离都不能小于D这个“最小距离”会被1拖垮。所以种3棵树时最大D只能取1选1、2、9或者1、2、8最小距离都是1。你看不是随便选最远的两个就完事这题的难点在于“M棵树之间彼此约束”。输入格式一般是两行第一行给出坑位数量N和需要种的树的数量M第二行给出N个坑位的坐标。输出就一个整数表示最大可能的最近距离。数据范围经常能到10^5甚至10^6级别的坐标所以暴力枚举所有组合方案想都不用想必炸。1.2 为什么不能直接排序后均匀分布有人会问是不是把坑位排序然后把最大坐标减最小坐标除以(M-1)不就是最大距离吗这个思路在坑位连续均匀分布时是对的但题目里的坑位是离散的、固定的你只能在给定坐标上种树不能凭空在中间插一个位置。比如 [1, 2, 100]要种2棵树按均分思路最大距离是(100-1)/(2-1)99但中间没有被占用的坑位实际只能选1和100距离是99这里碰巧一致。换成 [1, 50, 51, 100]种3棵树均分距离是(100-1)/249.5可实际上三个坑位要拉开49.5以上根本不可能因为50和51这个紧挨着的坑位决定了最小距离最多到不了50。所以这题必须换个思路与其正向构造方案不如反过来验证“给定一个距离能不能做到”。2. 核心解题思路二分答案 贪心校验2.1 把求最值问题变成判断问题这题的关键转换思维也是二分查找在高阶算法里最常见的应用——二分答案。我们不直接去求“最大最小距离”而是先猜一个距离D然后问自己一个问题在这个距离要求下能不能从坑位里挑出M个位置种树让任意两棵树的距离都≥D这个问题一旦问出来就有一个特别好的性质D越大越难满足。比如D100大概率种不下M棵树D1几乎怎么选都能种下。也就是说随着D从0一直增大到坐标跨度答案函数从“可行”变成“不可行”只会改变一次这个单调性就是二分查找能用的前提。如果满足单调性我们就可以用二分不断试探D找到那个“刚好还可行”的最大值。打个比方这就像你考试时猜一本词典的页数你说500页翻一下发现太厚了答案太大不可行说100页发现太薄了还能再大于是不断折中最后逼近真实页数。二分答案做的事情就是这个只不过判断“厚不厚”用的是贪心算法而不是翻词典。2.2 贪心校验函数能种就种判断函数是整道题的心脏。给定一个距离D怎么判断能不能种下M棵树正确做法是先把所有坑位坐标从小到大排序然后把第一棵树种在最左边的坑位接着从左往右遍历只要当前坑位和上一棵树的距离≥D就在这个坑位种下一棵树计数加一如果距离不够就继续往右找。最后如果计数≥M说明这个D是可行的。为什么这个贪心策略是正确的因为把第一棵种在最左边相当于给后面的树预留了最大的空间。任何时候只要当前坑位满足距离条件我们就没有理由跳过它——如果你跳过当前这个能种的坑位去种更靠右的坑位那么你以后每一棵树都会比“现在种”的方案更靠右留给后续树的空间只会更小绝不会更大。这就是“能种就种”的最优性证明考试时虽然不用写在代码里但心里要清楚它为什么对因为在判题现场面试官偶尔会追问思路。2.3 二分边界怎么写才不踩坑二分答案的模板我建议直接背熟不要每次现推。左边界low取0距离最小可以为0允许两棵树挤在同一个坑位其实题目通常保证有解且坑位坐标可能重复0也是合法下界右边界high取“最大坐标减去最小坐标”这是理论上的极限距离。在low ≤ high 的循环条件下每次取mid (low high) / 2调用校验函数如果check(mid)为真说明当前距离可行答案至少是mid我们往更大的方向试探low mid 1如果check(mid)为假说明距离太大种不下必须缩小high mid - 1。循环退出后high 就是我们要的答案。很多新手把low和high的更新写反或者最后输出low而不是high这是我见过最常见的错误。记住一个诀窍凡是“可行性为真往右走”的二分最终答案落在high上凡是“可行性为真往左走”的二分最终答案落在low上。这道题属于前者。def check(dist): cnt 1 # 第一棵种在最左边 last pos[0] for x in pos[1:]: if x - last dist: cnt 1 last x return cnt mcheck函数整体是O(N)二分次数是O(log(坐标范围))总体复杂度O(N log C)对于10^5数据量非常轻松。3. 五种语言完整实现与细节对比3.1 Java实现注意输入输出别拖后腿Java版本在华为OD机考中非常常见很多人担心排序和二分没问题结果栽在输入读取上。import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int[] pos new int[n]; for (int i 0; i n; i) { pos[i] sc.nextInt(); } Arrays.sort(pos); int low 0; int high pos[n - 1] - pos[0]; while (low high) { int mid (low high) / 2; if (check(pos, m, mid)) { low mid 1; } else { high mid - 1; } } System.out.println(high); } private static boolean check(int[] pos, int m, int dist) { int cnt 1; int last pos[0]; for (int i 1; i pos.length; i) { if (pos[i] - last dist) { cnt; last pos[i]; } } return cnt m; } }Java这里有一个非常值得注意的点当N很大比如10^6时用Scanner逐个数读取会明显变慢机考平台如果数据量大有超时风险。我个人的建议是直接用BufferedReader读取整行再split虽然代码啰嗦一点但稳定性高很多。另外一个很多人忽略的细节是(low high) / 2在极端情况下可能溢出Java中可以用low (high - low) / 2更安全。机考数据一般不会让你溢出但养成习惯没坏处。3.2 Python实现简洁但小心递归和输入Python写这道题非常清爽也是我最推荐用来快速验证思路的语言。def can_place(pos, m, dist): cnt 1 last pos[0] for x in pos[1:]: if x - last dist: cnt 1 last x return cnt m def main(): import sys input sys.stdin.readline n, m map(int, input().split()) pos list(map(int, input().split())) pos.sort() low, high 0, pos[-1] - pos[0] while low high: mid (low high) // 2 if can_place(pos, m, mid): low mid 1 else: high mid - 1 print(high) if __name__ __main__: main()Python易错点有两处。第一排序不要用sorted(pos, reverseTrue)之类搞错方向这题必须升序排列因为贪心从左往右种。第二输入要用sys.stdin.readline而不是input()如果N很大input()内部实现基于readline其实差别不大但多行场景下sys.stdin更稳。另外注意//是整数除法如果误写成/mid变成浮点数后面比较和切片都会出问题。我见过不止一个同学在机考现场因为Python浮点精度问题debug半小时其实根因就是/和//。3.3 JavaScript实现异步输入是最大的坎JS在OD机考中用的不多但既然题目要求覆盖还是要会。JS最容易出问题的是readline是异步的很多人把处理逻辑写在同步位置导致还没读到数据就开始二分结果输出undefined。function canPlace(pos, m, dist) { let cnt 1; let last pos[0]; for (let i 1; i pos.length; i) { if (pos[i] - last dist) { cnt; last pos[i]; } } return cnt m; } const readline require(readline); const rl readline.createInterface({ input: process.stdin }); let lines []; rl.on(line, (line) { lines.push(line.trim()); if (lines.length 2) { const [n, m] lines[0].split( ).map(Number); const pos lines[1].split( ).map(Number); pos.sort((a, b) a - b); let low 0; let high pos[n - 1] - pos[0]; while (low high) { const mid Math.floor((low high) / 2); if (canPlace(pos, m, mid)) { low mid 1; } else { high mid - 1; } } console.log(high); rl.close(); } });JS里最容易忽略的坑是sort()默认按字典序排序也就是把数字当成字符串比较[1, 2, 10]会被排成[1, 10, 2]结果全错。必须显式传比较函数(a, b) a - b。另一个坑是Math.floor((low high) / 2)JS没有整数除法直接/会得到小数的mid虽然二分最终也能收敛但可能额外多跑几次最好一次写对。3.4 C/C实现效率和写法都要兼顾C版本的代码适合追求极致效率的同学也是很多老手机考时的首选。#include bits/stdc.h using namespace std; bool canPlace(const vectorint pos, int m, int dist) { int cnt 1; int last pos[0]; for (int i 1; i (int)pos.size(); i) { if (pos[i] - last dist) { cnt; last pos[i]; } } return cnt m; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorint pos(n); for (int i 0; i n; i) { cin pos[i]; } sort(pos.begin(), pos.end()); int low 0; int high pos[n - 1] - pos[0]; while (low high) { int mid low (high - low) / 2; if (canPlace(pos, m, mid)) { low mid 1; } else { high mid - 1; } } cout high \n; return 0; }C有两个优化建议。第一是ios::sync_with_stdio(false); cin.tie(nullptr);这是机考C必须加的前缀不加的话cin读大数据量可能比scanf慢一个数量级。第二是#include bits/stdc.h这个万能头文件在华为OD机考平台通常能直接用也节省时间但有些编译器不支持。如果你用的是标准C环境就老老实实写#include iostream vector algorithm。如果坐标范围很大记得把int换成long long虽然常见数据范围int够用但题目没明确时用long long更保险。3.5 Go实现排序和扫描是重点Go的代码写起来比较“工程化”华为OD对Go的支持也越来越好尤其是后端岗位的同学可能会遇到。package main import ( fmt sort ) func canPlace(pos []int, m int, dist int) bool { cnt : 1 last : pos[0] for i : 1; i len(pos); i { if pos[i]-last dist { cnt last pos[i] } } return cnt m } func main() { var n, m int fmt.Scan(n, m) pos : make([]int, n) for i : 0; i n; i { fmt.Scan(pos[i]) } sort.Ints(pos) low, high : 0, pos[n-1]-pos[0] for low high { mid : low (high-low)/2 if canPlace(pos, m, mid) { low mid 1 } else { high mid - 1 } } fmt.Println(high) }Go的fmt.Scan在数据量大时其实效率一般但机考场景通常够用。如果性能要求严格可以用bufio.NewReader加strconv.Atoi手写读取不过那样代码量会变长面试时容易写乱。我更推荐先用fmt.Scan跑通再根据数据范围决定要不要优化。排序直接sort.IntsGo内置排序是改良后的快速排序性能和稳定性都可靠不用自己造轮子。3.6 五种语言代码对比总结维度JavaPythonJSCGo排序APIArrays.sortlist.sort()sort((a,b)a-b)sort()sort.Ints二分mid写法low(high-low)/2(lowhigh)//2Math.floor((lowhigh)/2)low(high-low)/2low(high-low)/2易错点Scanner慢、溢出/和//混用sort字典序输入锁Scan效率推荐场景企业级后端快速验证少量使用竞赛/性能敏感云原生/后端4. 机考双机位环境与实战注意事项4.1 双机位怎么布置才不会被判违规华为OD机考是远程在线机考采用双机位监考模式一个机位是正前方的电脑摄像头要求拍到你的脸和电脑屏幕另一个机位通常是手机或者平板放在你的侧后方大概45度角要求拍到你的手部、桌面和电脑屏幕。很多人以为双机位只是走个形式实际监考非常严格侧后方机位如果只拍到半个屏幕或者被手臂遮挡都有可能被判定环境异常。我自己的经验是提前准备好一个手机支架放在侧后方1.5米左右高度略高于桌面保证画面能同时看到你的双手和屏幕。考试开始前会有环境检测环节别嫌麻烦一定要在这个环节多调整几次把手机摄像头角度调到“双手完全不被遮挡”再进入考试。另外双机位意味着你在考试中低头写字、视线离开屏幕太久都可能被系统记录为疑似作弊所以草稿纸不要搞太复杂的演算尽量心算和屏幕内操作。4.2 在线编辑器的隐形坑机考平台不是本地IDE用的是在线编辑器这意味着三件事。第一有些语言是“自动补全不全”的比如Java的import java.util.*;必须自己写有些平台甚至不会给你带包建议每种语言都准备一套最短可运行模板考试开始前先默写一遍输入输出模板确保环境能跑通。第二代码里的调试输出一定要删干净有次我忘记删System.out.println(debug: mid)结果平台判我输出格式错误白白丢分。第三平台的语言版本可能和老代码不完全兼容比如C的bits/stdc.h在某些环境不支持Go的sort.Ints所有版本都支持但其他库函数要小心。还有一点机考通常不允许本地编译器所以你平时练习就要适应“没有报错高亮、没有自动格式化”的环境。我的建议是日常就用记事本或在线OJ写题不要一上来就开IDE不然考场打字速度和手感都会受影响。4.3 时间分配和代码调试策略双机位考试一般总时长有限C卷题目通常有2到3道编程题这道“最佳植树距离”属于中档偏基础的二分题理想情况下15到20分钟内应该完成。我的策略是先花5分钟读题和确认输入输出格式接着不急着写代码先在草稿纸上把check函数的逻辑写清楚然后直接套二分模板。如果样例过了不要立刻交自己构造几组边界数据测试一下N1时怎么处理、M等于N时答案是多少、所有坐标都相同时结果是不是0这些边界用例最能暴露问题。如果在调试中发现结果差一点首选检查排序方向然后是二分边界最后才怀疑check函数逻辑。按这个顺序排查通常一分钟内能找到问题。5. 高频报错与实战排查实录5.1 二分死循环low和high会不会卡住这个题目用while (low high)模板配合low mid 1和high mid - 1实际上不会死循环。但如果你用的模板是while (low high)并且更新写成了low mid或high mid就有可能在相邻整数之间无限循环。举个例子low3、high4mid3如果check(3)为真你写成lowmid那low永远是3死循环跑不出来。避免思路很简单记住“1”和“-1”的原则。只要mid不可行一定说明答案在左侧而且mid本身可以排除所以highmid-1只要mid可行答案至少是mid但我们还要找更大的所以lowmid1。这样每个循环区间至少缩小一半绝对不会死循环。5.2 答案比实际小1你说的是high还是low这是二分答案新手最容易犯的错。举个具体例子坑位[1, 3, 5]种2棵树正确答案是4选1和5距离4。假设low0、high4第一次mid2check(2)为真low变成3第二次mid3check(3)为真选1和5距离4≥3low变成4第三次mid4check(4)为真low变成5循环退出high4。输出high刚好是4。如果你习惯输出low就会得到5比正确答案大1。这个“大1”的问题根因在于最后一次mid可行时你已经把low推到了mid1low的含义是“第一个不可行/超出范围的值”high才是“最后一个可行的值”。所以我强烈建议所有“可行性为真往右走”的题目输出high。不想记的话就每次写完在样例上手动跑一遍二分看看最后low和high谁是对的然后固定下来这个模板。5.3 坐标数组没排序直接二分我自己也犯过这个低级错误。check函数假设坐标升序从左往右扫描但如果输入本身就是乱序的扫描过程中上一棵树可能在当前位置的右边距离变成负数判断逻辑全崩。正确做法是在main里一读入数组就排序这个操作必须在二分之前。Python里是pos.sort()Java是Arrays.sort(pos)JS记得加比较函数C用sort(pos.begin(), pos.end())。排序之后再也不要改动数组。从调试技巧上讲遇到结果反常时先打印一下排序后的数组确认排序有没有生效。很多时候问题不在二分而在排序。5.4 输入格式和平台相关的坑机考平台的输入有多种风格有的平台坐标在一行有的可能换行甚至可能有Windows下的\r换行符残留。处理办法是读取后用trim()去掉首尾空白按空格切分。我用JS时就踩过这个坑line.trim()忘写结果split后数组最后一项带上\r转成Number以后是个NaN整个程序全错。另外有些在线OJ要求多组输入直到EOF这道题一般是单组输入但万一遇到多组循环读取即可。我建议写代码时用一个函数封装核心逻辑main里只负责读数据和调用这样无论输入格式怎么变核心逻辑都不用动。5.5 时间和内存的极致优化空间大部分同学做到二分答案就已经能AC但如果你追求极致这里还有两个优化点。第一check函数里可以用一个变量记录上一次种树的位置这个已经做了还可以提前终止一旦cnt达到m就立刻返回true不需要扫描完整数组在D比较小、树很多时能省不少时间。第二二分上界可以不用“最大坐标减最小坐标”而是用“坐标跨度除以(M-1)”这个上界更紧凑能减少二分次数。虽然对本题影响不大但对追求极致性能的比赛来说是常规优化。bool canPlace(const vectorint pos, int m, int dist) { int cnt 1; int last pos[0]; for (int i 1; i (int)pos.size(); i) { if (pos[i] - last dist) { cnt; if (cnt m) return true; last pos[i]; } } return false; }5.6 同类题举一反三这道题的价值不止于OD“最佳植树距离”其实就是经典的“Aggressive cows”问题换了个马甲核心模型是“在离散坐标上选M个点最大化最小间距”。这类题的变体非常多比如“放置广告牌”、“安排工位”、“给比赛选手分配休息室”全都是同一个套路。你只要掌握了二分答案贪心校验的组合等于一次性会做一类题而不只是一道题。再延伸一步二分答案还能处理“最小化最大值”的问题思路完全镜像把check函数从“能否种下”改成“能否不超过”同样是利用答案的单调性。遇到这类题先不要慌往二分答案的方向想十有八九是对的。最后分享一点我的实战体会这道题我前后用五种语言各写过一遍最大的体会是算法思路一旦透了语言只是表达方式的差异。真正让我丢分的从来不是二分不会写而是输入读取失败、排序方向写反、忘了删调试输出这些看起来“低级”的细节。准备华为OD机考的同学考前一定要把每种语言的输入输出模板背到形成肌肉记忆再配合刷几道二分答案的题考场上就会稳很多。后边如果再遇到类似的“牛舍问题”“分割数组”变体你就知道该怎么拆了。