题面描述
云某公司在基地搬迁到新地点后，规划了一条经过 N 个小区的班车路线。公司计划在这些小区中挑选出 M 个小区作为上车点。小区的位置可以用一维坐标上的整数点表示。每个小区到最近上车点的距离为这两个坐标点差值的绝对值。若小区本身被选为上车点，则其到上车点的距离为 0。
任务：在给定 N 个小区的位置的情况下，选择 M 个上车点，使得所有小区到最近上车点的距离的最大值尽可能小。计算这个最大值的最小值。
思路
二分答案。二分这个最小可能值mid，如何check呢?我们贪心的考虑，我们放车站的时候尽可能大的覆盖到右边的区域，最多能覆盖盖positions[i]+mid这个位置，我们将下一个位置跳到`
upper_bound(positions.begin(), positions.end(),positions[i] + mid) - positions.begin();
P2639.公司班车上车点规划-让最远的员工少走点路
题目内容
某公司基地搬迁到新地点之后，新规划了一条班车路线，在这条路线上会经过 N 个小区，计划在这些小区中挑选出 M 个作为上车点，小区的位置可以用一维坐标上的点来表示，小区到上车点的距离为两个坐标点差值的绝对值。现在给定 N 个小区的位置，即一维坐标上的整数点：x1、x2、...、xN ，我们希望所有小区到最近上车点的距离总和尽可能小，请计算这个最大值能够是多少？当该小区被作为上车点，该小区到上车点的距离为 0 。
输入描述
第一行有两个整数，用空格隔开：N M ，1<M<=N<=100000
第二行有 N 个没有重复的递增的整数，用空格隔开，表示 N 个小区的位置，1<=xi<=1000000
输出描述
一个整数，表示所有小区到上车点距离的最大值的最小值
样例1
输入
5 2
1 2 3 6 7
输出
1
说明
将上车点设置在 2、6 这两个小区时，所有小区到上车点距离的最大值的最小值为 1 。
样例2
输入
10 5
1 2 3 6 7 9 11 22 44 50
输出
3
说明
将上车点设置在 2、9、22、44、50 这 5 个小区时，所有小区到上车点距离的最大值的最小值为 3 。
