CJBS05｜安装信号站 题解

核心算法

排序坐标，二分最小间距；检查时从左到右贪心地尽早放置信号站。

思路推导

给定距离 $D$，先在最左位置放一个站，之后每次选择第一个与上一个已选位置距离至少为 $D$ 的候选点。这种选择给剩余站留下最大的空间。如果能放到至少 $k$ 个，则 $D$ 可行；更小距离也一定可行。

正确性说明

对于固定 $D$，贪心选择的第 $j$ 个站不会位于任何可行方案第 $j$ 个站的右侧。用归纳即可证明：选择越靠左，给后续留下的位置只会更多。因此若贪心都无法放满 $k$ 个，其他方案也不可能；若能放满，$D$ 可行。再由可行性的单调性，二分可得到最大可行距离。

复杂度

• 排序：$O(n\log n)$；
• 每次检查：$O(n)$；
• 总时间：$O(n\log n+n\log 10^9)$；
• 空间：$O(n)$。

易错点

• 输入坐标不保证有序，必须排序；
• 第一个站可以固定在最左端；
• 判断条件是距离 >= D；
• 二分目标是最大可行值，更新方向不能写反。