P3303. 最佳植树距离

解题思路

二段性分析

考虑最小种植间距 interval 与可种植树木数量之间的关系：

• 最小种植间距 interval 越大的时候，在原列表 trees 中只能种下越少的树。当取到最值 interval = max(trees) - min(trees) 时，则只能在头尾种下 2 棵树，可种植树木数量为 2。
• 最小种植间距 interval 越小的时候，在原列表 trees 中可以种下越多的树。当取到最值 interval = 1 时，所有坑位都能种下树木，可种植树木数量为 `len(trees)`。

对于在区间 [1, max(trees) - min(trees)] 之间取值的最小种植间距 interval 而言，一定存在一个值 `ans`，使得：

• 当 interval ∈ [1, ans] 时，可以种下 N 棵树。
• 当 interval ∈ (ans, max(trees)] 时，不能种下 N 棵树。

这体现了这个问题的二段性，ans 是我们需要的答案，而 ans 的寻找就可以用二分查找来完成。

故二分查找的框架为：

子问题分析

对于二分查找过程中得到的每一个最小种植间距 interval = mid，我们都要去判断在该间距的条件下 trees 数组能否成功种下 N 棵树。对于这个问题，我们可以用贪心的思路来解决：

• 我们需要先对 trees 数组以升序排序，这样才能方便统计相邻坑位距离。
• 我们已知前一棵树的位置是 pre_tree，那么对于当前树位置 cur_tree，当：
• 当前树 cur_tree 和上一棵树 pre_tree 的距离大于等于最小种植间距 interval，我们种下当前树，种下树的总数 num 增加 1。同时，对于后面的树而言，当前树 cur_tree 成了其上一棵树，故修改上一棵树的变量 pre_tree = cur_tree。
• 当前树 cur_tree 和上一棵树 pre_tree 的距离小于最小种植间距 interval，无法种下当前树，pre_tree 也无需做出任何修改。
• 由于第一个位置肯定贪心地被种下，因此种下的数目 num 初始化为 1，同时初始化 pre_tree = trees[0] 即为第一棵树的位置。

上述逻辑整理为代码即构建 check_available(interval, trees, N) 函数：

复杂度分析 设 M 为坑位数量（数组 trees 的长度），D 为首尾坑位的坐标差 trees[-1] - trees[0]。

• check_available 从第二个坑位起做一趟线性扫描，用 pre_tree 记录上一棵已种的树、贪心统计能种下的数量，单次调用为 O(M)。
• 二分在间距的取值范围 [1, D+1) 上进行，迭代次数为 O(log D)，每轮调用一次 check_available。

因此总时间复杂度为 O(M log D)：二分负责收缩间距取值，线性检查负责验证该间距下能否种满 N 棵树。空间上 check_available 只用 num、pre_tree 两个变量，加上二分的 left、right、mid，除输入数组外额外空间复杂度为 O(1)。