如果你最近在刷大厂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 距离 45 和 10 距离 5最小距离是 4。可是如果你反过来枚举一下方案 1、5、10 确实是最优的最小距离 4但方案 1、4、10 最小距离是 31、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 完整流程与时间复杂度整体流程四步读入 n、k 和坐标数组。对坐标数组从小到大排序。在 [0, maxPos - minPos] 区间上二分。每次用 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 的机考数据下完全不可行。也有人会想直接算相邻坐标差值的最小值行不行那是 kn 的特例如果 k 比 n 小得多答案会变大。比如位置 1 2 100 101k2 时答案显然是 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看起来没问题但遇到 k2、坐标一长串的情况白白多扫很多元素。机考数据如果给到 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 各语言易错点对照表语言最容易出问题的地方我的推荐写法JavaScanner 读大输入偏慢二分 mid 可能溢出BufferedReader StringTokenizermid l (r - l) / 2Python逐行读容易漏行忘记处理空输入sys.stdin.read().split()一次性读取JavaScript异步输入导致主逻辑被拆分空行污染 tokens收集所有非空行在close回调里统一处理C数组开太小头文件不被支持开足够大的全局数组必要时换标准头文件Go误以为 sort.Ints 返回新切片Fscan 类型不匹配确认原地排序输入格式固定时可放心 Fscan5. 机考现场最容易丢分的几个点输入格式、二分上下界、自测节奏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。这是这题最阴险的边界用例之一。如果 k1按题意“只种一棵树”任意间距都可行理论答案应该是坐标跨度。我的 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 之间的距离。用例3k 等于 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)死循环问题。如果真不确定就拿l0, r3, mid1这种小范围在草稿纸上手动推几步推完再写进编辑器。在双机位环境下你唯一能依赖的调试手段就是自己的脑子提前把模板固定下来考试时才不会慌。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 函数里的边界和特判。多练几道同类型题把这套流程变成肌肉记忆考场上的心态会完全不一样。
如果你最近在刷大厂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 距离 45 和 10 距离 5最小距离是 4。可是如果你反过来枚举一下方案 1、5、10 确实是最优的最小距离 4但方案 1、4、10 最小距离是 31、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 完整流程与时间复杂度整体流程四步读入 n、k 和坐标数组。对坐标数组从小到大排序。在 [0, maxPos - minPos] 区间上二分。每次用 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 的机考数据下完全不可行。也有人会想直接算相邻坐标差值的最小值行不行那是 kn 的特例如果 k 比 n 小得多答案会变大。比如位置 1 2 100 101k2 时答案显然是 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看起来没问题但遇到 k2、坐标一长串的情况白白多扫很多元素。机考数据如果给到 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 各语言易错点对照表语言最容易出问题的地方我的推荐写法JavaScanner 读大输入偏慢二分 mid 可能溢出BufferedReader StringTokenizermid l (r - l) / 2Python逐行读容易漏行忘记处理空输入sys.stdin.read().split()一次性读取JavaScript异步输入导致主逻辑被拆分空行污染 tokens收集所有非空行在close回调里统一处理C数组开太小头文件不被支持开足够大的全局数组必要时换标准头文件Go误以为 sort.Ints 返回新切片Fscan 类型不匹配确认原地排序输入格式固定时可放心 Fscan5. 机考现场最容易丢分的几个点输入格式、二分上下界、自测节奏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。这是这题最阴险的边界用例之一。如果 k1按题意“只种一棵树”任意间距都可行理论答案应该是坐标跨度。我的 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 之间的距离。用例3k 等于 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)死循环问题。如果真不确定就拿l0, r3, mid1这种小范围在草稿纸上手动推几步推完再写进编辑器。在双机位环境下你唯一能依赖的调试手段就是自己的脑子提前把模板固定下来考试时才不会慌。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 函数里的边界和特判。多练几道同类型题把这套流程变成肌肉记忆考场上的心态会完全不一样。
