华为OD机考“最佳植树距离”解题：二分答案+贪心校验全解析

最近不少同学在准备华为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)/2=49.5，可实际上三个坑位要拉开49.5以上根本不可能，因为50和51这个紧挨着的坑位决定了最小距离最多到不了50。所以这题必须换个思路：与其正向构造方案，不如反过来验证“给定一个距离，能不能做到”。

2. 核心解题思路：二分答案 + 贪心校验

2.1 把求最值问题变成判断问题

这题的关键转换思维，也是二分查找在高阶算法里最常见的应用——二分答案。我们不直接去求“最大最小距离”，而是先猜一个距离D，然后问自己一个问题：在这个距离要求下，能不能从坑位里挑出M个位置种树，让任意两棵树的距离都≥D？

这个问题一旦问出来，就有一个特别好的性质：D越大，越难满足。比如D=100大概率种不下M棵树，D=1几乎怎么选都能种下。也就是说，随着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 >= m

check函数整体是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, reverse=True)之类搞错方向，这题必须升序排列，因为贪心从左往右种。第二，输入要用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 vector<int>& 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; vector<int> 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.Ints，Go内置排序是改良后的快速排序，性能和稳定性都可靠，不用自己造轮子。

3.6 五种语言代码对比总结

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函数的逻辑写清楚，然后直接套二分模板。如果样例过了，不要立刻交，自己构造几组边界数据测试一下：N=1时怎么处理、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，就有可能在相邻整数之间无限循环。举个例子，low=3、high=4，mid=3，如果check(3)为真，你写成low=mid，那low永远是3，死循环跑不出来。

避免思路很简单：记住“+1”和“-1”的原则。只要mid不可行，一定说明答案在左侧，而且mid本身可以排除，所以high=mid-1；只要mid可行，答案至少是mid，但我们还要找更大的，所以low=mid+1。这样每个循环区间至少缩小一半，绝对不会死循环。

5.2 答案比实际小1：你说的是high还是low

这是二分答案新手最容易犯的错。举个具体例子：坑位[1, 3, 5]，种2棵树，正确答案是4（选1和5距离4）。假设low=0、high=4，第一次mid=2，check(2)为真，low变成3；第二次mid=3，check(3)为真（选1和5距离4≥3），low变成4；第三次mid=4，check(4)为真，low变成5；循环退出，high=4。输出high刚好是4。如果你习惯输出low，就会得到5，比正确答案大1。

这个“大1”的问题根因在于：最后一次mid可行时，你已经把low推到了mid+1，low的含义是“第一个不可行/超出范围的值”，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 vector<int>& 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机考的同学，考前一定要把每种语言的输入输出模板背到形成肌肉记忆，再配合刷几道二分答案的题，考场上就会稳很多。后边如果再遇到类似的“牛舍问题”“分割数组”变体，你就知道该怎么拆了。