企业官网建设流程全解析

如果你最近在刷大厂OD机考C卷的算法题库，“最佳植树距离”这个名字大概率不会陌生。题目本身是个典型的二分答案题：给你一串可用的植树位置，要种K棵树，问怎么安排能让“最近的两棵树之间的距离”尽可能大。看着像贪心，实际藏着一个二分框架，很多人第一眼都会被带偏。我最初在双机位监控下写这题时，sort 完就直接去模拟“间距最大”，结果样例能过、边界全挂，Debug 到心态崩。这篇文章把自己踩过的坑、推导思路和五种语言实现全部整理出来，给正在准备机考的朋友做个参考。

1. 题目到底在问什么：先把它改写成能动手写的需求

1.1 输入输出与原题描述

原题经过平台转写后，通常会描述成一个“绿化场景”：某条规划道路边上有 n 个已经打好的树坑，每个坑有一个坐标位置，现在准备种 k 棵树。为了让树苗之间互不遮挡，要求任意两棵树的直线距离不能太小，并且希望在满足“至少种 k 棵”的前提下，让这个“最小间距”尽量大。

翻译成程序语言就是：

输入第一行：n 和 k，表示共有 n 个可用位置，要种 k 棵树。 输入第二行：n 个整数，表示每个位置的坐标。 输出：一个整数，表示在最优种植方案中，最近两棵树的距离的最大值。

拿一个样例说话：

输入： 5 3 1 2 4 8 9 输出： 3

解释一下这个输出：位置 1、4、8 三棵树，最近距离是 min(3, 4) = 3；位置 1、4、9 也一样，最近距离是 3。你可能会疑惑，为什么不是 4？因为 8 和 9 这两个位置靠得近，一旦要种 3 棵树，你必然要牺牲掉某个大间距来换取“树的数量足够”。这也是这题的核心矛盾：树越多，能维持的最小间隔就越小。

1.2 为什么“排个序直接种”会翻车

没接触过二分答案的人，很自然会想到：先把坐标排序，然后两两之间的距离排个序，从大到小尽量选不冲突的位置。这个思路听起来顺，但实现起来全是坑。

举个例子：

n = 5, k = 3 位置：1 4 5 8 10

如果你先找全数组里最远的一对，也就是 1 和 10，把它们种上，然后从剩余位置里找一个能让“三棵树最小距离最大”的点，直觉上会选 5，因为 1 和 5 距离 4，5 和 10 距离 5，最小距离是 4。可是如果你反过来枚举一下，方案 1、5、10 确实是最优的，最小距离 4；但方案 1、4、10 最小距离是 3，1、5、8 最小距离也是 3。如果按照“先选最远两端”的贪心策略，你会拿到 1、4、10 或者 1、5、10？取决于你第二步怎么选，并不稳定。

更关键的是，贪心策略没有一个清晰的“全局判断标准”。你没法简单地证明“每次都挑最远未冲突的点，最后结果一定最大”。这类的“最小距离最大化”问题，标准解法就是二分答案：把“间距不能小于多少”当作一个条件去尝试，然后验证能不能种够 k 棵。

2. 主框架：二分答案为什么是这题的“标准答案”

2.1 单调性：从“距离能不能做到”看二分

二分答案的精髓，是把“求最优值”转换成“判断某个值是否可行”。

对于这道题，假设我们给定一个距离 d，问：能不能在 n 个位置里选出 k 个植树点，使得任意两棵树的间距都不小于 d？

这个“能不能做到”的函数，一定是单调的：如果 d = 3 能做到，那么 d = 2 也一定能做到，因为间距限制放宽了；反过来，如果 d = 3 做不到，那 d = 4 也一定做不到，因为条件更严格了。

所以答案就可以在一段区间里二分。区间左端是 0（所有树同一位置也能种的最小极限），右端是坐标最大值减最小值（两棵树的极限距离不可能超过整个区间的跨度）。每次取中值 mid，调用一个 check(mid) 函数判断 mid 这个间距是否可行。可行就把答案更新为 mid，并往更大的方向试；不可行就往更小的方向试。

2.2 完整流程与时间复杂度

整体流程四步：

1. 读入 n、k 和坐标数组。
2. 对坐标数组从小到大排序。
3. 在 [0, maxPos - minPos] 区间上二分。
4. 每次用 check(mid) 做可行性判断，最终输出最优答案。

时间复杂度是排序的 O(n log n)，加上二分次数乘以每次 check 的 O(n)。坐标范围如果不超过 10^9，二分次数大约是 log2(10^9) ≈ 30 次，整体很快。这也是为什么这个题对五种语言都很友好：没有任何需要高级数据结构的环节，一个排序、一个循环、一个二分框架，就能稳过。

2.3 为什么不建议换其他思路

有人会问，能不能用动态规划？状态如果定义成“前 i 个位置选了 j 棵树的最大间距”，需要 O(n*k) 个状态，转移又要枚举上一棵树的位置，复杂度 O(n^2 * k)，在 n 和 k 都到 10^5 的机考数据下完全不可行。

也有人会想，直接算相邻坐标差值的最小值行不行？那是 k=n 的特例；如果 k 比 n 小得多，答案会变大。比如位置 1 2 100 101，k=2 时答案显然是 100，但相邻坐标最小差值是 1，完全对不上。

这类“最大值最小”“最小值最大”的题，只要数据规模大，基本都是二分答案的天下。最佳植树距离就是标准的二分答案模板题，早认清这一点，后面代码写起来会非常顺。

3. check函数的贪心验证：核心就三行，但边界问题都在这

3.1 贪心验证的推导：从第一棵树开始种的理由

check(mid) 的实现思路是贪心：在排序后的坐标上，从第一个位置种下第一棵树，然后往后扫，只要发现某个位置和上一棵树的距离不小于 mid，就在这里种下一棵。如果能种满 k 棵，返回 true，否则返回 false。

为什么这个贪心是成立的？关键在于“第一棵树一定种在第一个坐标上”。如果某个可行方案的第一棵树不在第一个坐标，那我把它移动到第一个坐标，会影响什么？从第一个坐标到第二棵树之间的距离只会变大，不会变小，所以后面的树仍然都能满足间距要求。既然移动不会破坏可行性，那最优方案总能假设第一棵树在坐标数组的第一个位置。

一旦第一棵树位置固定，后面的选择就变得很机械：距离足够时就种，不够就跳过。因为在单方向上，越早种树，留给后面的空间越多；种在尽可能靠左的、满足距离要求的位置，永远不会比种在更靠右的位置差。这就是贪心正确性的核心。

3.2 边界细节：cnt 从 1 开始，last 的更新时机

check 函数写起来非常短，但几个细节必须抠清楚：

• cnt 初始值必须是 1，因为第一棵树已经种在 pos[0] 上了。
• last 记录上一棵树的坐标，初始化也是 pos[0]。
• 遍历 i 从 1 到 n-1，遇到 pos[i] - last >= d 时，cnt 加一，last 更新为 pos[i]。
• 循环途中如果 cnt 已经达到 k，直接返回 true，不需要继续扫。
• 循环结束后如果 cnt 还是小于 k，说明 mid 太大，种不够 k 棵树，返回 false。

有一种容易犯的错：有人会把 cnt 初始化为 0，然后在循环里对第一个位置也判断一遍。这样不会错，但要多写一个“是否种了第一棵树”的判断，代码不干净。更推荐直接种第一棵在 pos[0]，因为第一棵的位置不需要挑选。

3.3 一个容易忽略的优化：提前退出

check 里的提前退出不只是优化，也是防超时的关键。当 k 很大、mid 很小时，可能扫到数组一半就种满了，及时 return true 能省不少时间。反过来，mid 很大时可能扫完整个数组也种不满，那也必须把数组扫完才能 return false。

这个提前退出的位置，我建议写在 cnt 自增之后。很多参考代码喜欢在循环外统一 return cnt >= k，看起来没问题，但遇到 k=2、坐标一长串的情况，白白多扫很多元素。机考数据如果给到 10^5，多扫几轮虽然不至于超时，但没必要。写代码时把“能早停就早停”当成默认习惯，总没坏处。

4. 五语言代码逐行解读与踩坑对照

4.1 Java 实现：用 BufferedReader 读入，注意二分写法

在线判题环境里，Java 用 Scanner 读 10^5 个整数虽然也能过，但性能一般。习惯上我建议用 BufferedReader + StringTokenizer，反正代码量差别不大。

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); st = new StringTokenizer(br.readLine()); int[] pos = new int[n]; for (int i = 0; i < n; i++) { pos[i] = Integer.parseInt(st.nextToken()); } Arrays.sort(pos); int l = 0; int r = pos[n - 1] - pos[0]; int ans = 0; while (l <= r) { int mid = l + (r - l) / 2; if (check(pos, k, mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } System.out.println(ans); } private static boolean check(int[] pos, int k, int d) { int cnt = 1; int last = pos[0]; for (int i = 1; i < pos.length; i++) { if (pos[i] - last >= d) { cnt++; last = pos[i]; if (cnt >= k) { return true; } } } return false; } }

这里有一个很细节的点：mid 用l + (r - l) / 2而不是(l + r) / 2。虽然这道题坐标最大 10^9，两者都不溢出，但 OJ 上有些题会设置到 2^31 附近的数据范围，养成这个习惯以后写别的二分也不会翻车。while (l <= r)的模板是带着 ans 变量的写法，比l < r的写法更适合机考这种高压场景，因为答案会被显式保存，不怕边界死循环。

4.2 Python 实现：sys.stdin.read 一次读完，简单清爽

Python 写这题是最快的，关键是读入别再一行一行折腾，直接用sys.stdin.read()把整个输入变成 token 列表，干净利落。

import sys def can_plant(pos, k, d): cnt = 1 last = pos[0] for x in pos[1:]: if x - last >= d: cnt += 1 last = x if cnt >= k: return True return False def main(): data = list(map(int, sys.stdin.read().split())) if not data: return n, k = data[0], data[1] pos = sorted(data[2:2 + n]) l, r, ans = 0, pos[-1] - pos[0], 0 while l <= r: mid = (l + r) // 2 if can_plant(pos, k, mid): ans = mid l = mid + 1 else: r = mid - 1 print(ans) if __name__ == "__main__": main()

Python 的pos[1:]会复制列表，好在数据规模 10^5 时无所谓。如果你想要极致省内存，可以改成for i in range(1, len(pos))。不过机考一般在同一个平台跑多个语言，同样数据量下 Python 这个写法足够跑进时限。注意if not data这行最好留着，因为有的 OJ 输入末尾会有奇怪空行，read 出来可能是空串。

4.3 JavaScript 实现：readline 的异步回调与空行处理

Node.js 环境写算法题，最难受的是输入不是同步的。readline 的line事件会被多次回调，必须先把所有行收集起来，等close后再统一处理。

const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin }); const tokens = []; rl.on('line', (line) => { const trimmed = line.trim(); if (trimmed !== '') { tokens.push(...trimmed.split(/\s+/).map(Number)); } }); rl.on('close', () => { const n = tokens[0]; const k = tokens[1]; const pos = tokens.slice(2, 2 + n).sort((a, b) => a - b); const check = (d) => { let cnt = 1; let last = pos[0]; for (let i = 1; i < n; i++) { if (pos[i] - last >= d) { cnt++; last = pos[i]; if (cnt >= k) return true; } } return false; }; let l = 0; let r = pos[n - 1] - pos[0]; let ans = 0; while (l <= r) { const mid = Math.floor((l + r) / 2); if (check(mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } console.log(ans); });

这里最容易被忽略的是空行判断。如果不加trimmed !== ''的判断，一个空行经过split(/\s+/)会得到['']，再map(Number)就变成0，污染 tokens 数组。平时本地控制台不会有空行，但 OJ 的测试文件末尾有时候会多一个换行，严谨一点总没错。

4.4 C++ 实现：scanf 与全局数组，Check 函数返回提前退出

C++ 写算法题，性能不是问题，问题在于代码冗长。我习惯用scanf+ 全局数组，这样 check 函数可以直接访问数组，少传几个参数。

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int n, k; int pos[MAXN]; bool check(int d) { int cnt = 1; int last = pos[0]; for (int i = 1; i < n; i++) { if (pos[i] - last >= d) { cnt++; last = pos[i]; if (cnt >= k) return true; } } return false; } int main() { scanf("%d%d", &n, &k); for (int i = 0; i < n; i++) { scanf("%d", &pos[i]); } sort(pos, pos + n); int l = 0; int r = pos[n - 1] - pos[0]; int ans = 0; while (l <= r) { int mid = l + (r - l) / 2; if (check(mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } printf("%d\n", ans); return 0; }

C++ 的坑主要在MAXN开多大。机考一般 n 最大 10^5，开 100005 没问题；如果你不确定，直接开 1000005 也不影响。另外头文件用<bits/stdc++.h>在 OJ 上普遍支持，但在某些严格标准环境下会报错，如果平台不支持，可以换成常用的iostream、algorithm、cstdio组合。

4.5 Go 实现：fmt.Fscan 和 sort.Ints 的配合

Go 写算法题的体验很稳，标准库sort.Ints直接排序，fmt.Fscan会自动跳过空白字符，处理输入很省心。

package main import ( "bufio" "fmt" "os" "sort" ) func canPlant(pos []int, k, d int) bool { cnt := 1 last := pos[0] for i := 1; i < len(pos); i++ { if pos[i]-last >= d { cnt++ last = pos[i] if cnt >= k { return true } } } return false } func main() { in := bufio.NewReader(os.Stdin) var n, k int fmt.Fscan(in, &n, &k) pos := make([]int, n) for i := 0; i < n; i++ { fmt.Fscan(in, &pos[i]) } sort.Ints(pos) l, r, ans := 0, pos[n-1]-pos[0], 0 for l <= r { mid := l + (r-l)/2 if canPlant(pos, k, mid) { ans = mid l = mid + 1 } else { r = mid - 1 } } fmt.Println(ans) }

Go 初学者最容易犯的毛病是忘了sort.Ints是原地排序，而不是返回新切片；以及fmt.Fscan如果遇到类型不匹配会把错误吞掉，导致变量留零值。机考时输入必定是合法整数，这个问题一般不会触发，但心里有数就好。

4.6 各语言易错点对照表

5. 机考现场最容易丢分的几个点：输入格式、二分上下界、自测节奏

5.1 读取数据的三种坑：空行、末尾空格、多个测试用例

机考的判题输入通常来自文件重定向，肉眼看不见行尾情况。第二行的坐标可能全在一行，也可能被折成多行；更常见的是每行末尾多一个空格。用split()或者StringTokenizer这类按空白拆分的方案天然兼容这两种情况，所以前面所有代码都推荐“把一整个输入流拆成 token”。

还有一个机考容易被忽略的问题：多个测试用例时，平台可能在每个用例之间插空行。如果题目说明是单组输入，那没关系；如果不确定，最好用while循环读到 EOF，每次读一组处理一组。不过“最佳植树距离”这套题在 C 卷里基本都是单组输入，我写单组版本就够了。你要是想更保险，可以在循环里加if (!br.ready()) break之类的判断，但别把主逻辑搞复杂。

5.2 二分上下界怎么取：别从 0 到 1e9 硬写

二分右边界最好取pos[n-1] - pos[0]，也就是坐标最大值减最小值。有人图省事把右边界设成 1e9，二分轮数会多几次，但 30 和 31 次没区别。真正的问题在左边界：能不能从 1 开始？如果所有坐标都相同，比如3 3 / 1 1 1，答案是 0，左边界取 1 会导致一开始就误判为不可行，输出错误。所以左边界必须从 0 开始，ans 初始化也必须是 0。这是这题最阴险的边界用例之一。

如果 k=1，按题意“只种一棵树”，任意间距都可行，理论答案应该是坐标跨度。我的 check 函数里 cnt 初始为 1，对于任意 d 都会返回 true，二分最后 ans 会等于右边界 pos[n-1] - pos[0]，逻辑上刚好成立。不过大多数机考题会保证 k >= 2，你不需要刻意处理。

5.3 提交前必测的几组用例

每次写完算法，别急着提交。先用这几组数据自测：

用例1：基本样例 5 3 1 2 4 8 9 期望输出：3

用例2：只种两棵树 5 2 1 2 4 8 9 期望输出：8

两棵树时，答案就是最大跨度 8，也就是 1 和 9 之间的距离。

用例3：k 等于 n，所有位置都种 5 5 1 2 4 8 9 期望输出：1

所有坑都种，最近距离是相邻坐标差值的最小值，即 min(1,2,4,1)=1。

用例4：所有位置重叠 3 3 1 1 1 期望输出：0

这个用例专门验证左边界和 ans 初始值。

用例5：坐标跨度很大但中间位置稀疏 4 2 0 1000000000 1000000000 1000000000 期望输出：1000000000

注意读入坐标时，某些语言里1000000000仍在 int 范围内，但如果你把右边界初始化为int(1e9)后，再用l + (r-l)/2计算，安全。

5.4 双机位下如何快速定位二分死循环

OD 机考现在普遍要求双机位监控，考试时不能切屏查资料，也没有太多时间反复试错。一旦你发现二分跑不出答案，最有效的定位方式不是看全代码，而是打印中间值，但这在 OJ 上是禁止的，因为判题程序会比对输出流。

所以在写代码前就要把二分框架写对。我的建议是优先使用带 ans 的while (l <= r)模板。这个模板不会出现常见的while (l < r)死循环问题。如果真不确定，就拿l=0, r=3, mid=1这种小范围在草稿纸上手动推几步，推完再写进编辑器。在双机位环境下，你唯一能依赖的调试手段就是自己的脑子，提前把模板固定下来，考试时才不会慌。

6. 复盘与举一反三：认出“最大化最小值”这一族题型

6.1 识别信号：题面里出现“最近距离尽量大”“让最小的……最大”

“最佳植树距离”这题真正的考点不是植树，而是你能不能看出它属于“最大化最小值”问题。这类题的标志性描述通常是：

• “让最近的两者之间的距离尽可能大”
• “最小间隔的最大值是多少”
• “所有方案中，较劣的那个环节尽量被优化”

一旦在题面里看到这种说法，第一反应就应该是二分答案。把“最小间隔最大”转成“给定间隔 d，判断是否可行”，然后套二分框架。类似的题还有“放置快递柜”“选择开会时间”“分巧克力”等等，模型都一样：在候选值域上二分，用贪心或简单条件做 check。

6.2 变式：坑位不是整数、需要输出种植方案、树可以种在任意实数坐标

如果题干改成“树可以种在任意实数位置，不限于给定坑位”，那这题会变得非常朴素：答案就是(maxPos - minPos) / (k - 1)，因为你可以把 k 棵树均匀分布在区间两端之间。但机考里为了增加难度，通常会把位置限定成离散坐标，这才需要二分。

另一种变式是要求输出具体种在哪些位置。此时 check 函数里不要只维护 cnt，还要额外记录下每次种树的位置，最后把记录结果打印出来。逻辑上的改动不大，但要注意顺序：二分答案确定之后，还要再调用一次 check 来生成方案，不能直接在二分过程中保存，因为最后一次成功的那次 mid 不一定等于最终 ans，至少不保险。

还有一种变式是把坐标数组换成二维平面上的点，问题就升级成了“最大化最近点对的距离”，那就不是简单贪心能解决的了。机考 C 卷通常不会到这一步，但如果后续刷题遇到，请记住基本策略依然是二分答案，只是 check 函数里要用更复杂的数据结构去判断某个半径范围能否放入 k 个点。

6.3 我常用的答题节奏与心法

我的个人习惯是：拿到这类题，先花一分钟确认“最大化”的东西到底是什么。最佳植树距离最大化的是“最近距离”，而“最近距离”本身是一个间距。确认完之后，直接把 check 函数写出来，再套二分。这样即使后面时间紧张，核心逻辑也已经稳了。

还有一个小技巧：把所有边界用例提前写在注释里，比如// k == n 时答案为相邻最小差值、// 坐标重复时答案为 0，这样写主逻辑的时候就不会遗忘边界。机考真正比拼的不是你会不会一种算法，而是你有没有一套稳定的复现流程。二分答案的框架其实很简单，难的是每次 check 函数里的边界和特判。多练几道同类型题，把这套流程变成肌肉记忆，考场上的心态会完全不一样。