题目内容

云某公司基地搬迁到新地点之后，新规划了一条班车路线，在这条路线上会经过$N$个小区，计划在这些小区中挑选出$M$个作为上车点，小区的位置可以用一维坐标上的点来表示，小区到上车点的距离为两个坐标点差值的绝对值。

现在给定$N$个小区的位置，即一维坐标上的整数点:$x1、x2....xN$，我们希望所有小区到最近上车点的距离的最大值尽可能小，请计算这个最大值的最小值能够是多少?当该小区被作为上车点，该小区到上车点的距离为$0$。

题面描述

云某公司在基地搬迁到新地点后，规划了一条经过 $N$ 个小区的班车路线。公司计划在这些小区中挑选出 $M$ 个小区作为上车点。小区的位置可以用一维坐标上的整数点表示。每个小区到最近上车点的距离为这两个坐标点差值的绝对值。若小区本身被选为上车点，则其到上车点的距离为 $0$。

任务：在给定 $N$ 个小区的位置的情况下，选择 $M$ 个上车点，使得所有小区到最近上车点的距离的最大值尽可能小。计算这个最大值的最小值。

思路

二分答案。二分这个最小可能值$mid$，如何$check$呢?我们贪心的考虑，我们放车站的时候尽可能大的覆盖到右边的区域，最多能覆盖盖$positions[i] + mid$这个位置，我们将下一个位置跳到upper_bound(positions.begin(), positions.end(),positions[i] + mid) - positions.begin();即可，最后检查车站数量是否不超过m即可