第 25 场 蓝桥入门赛
题目：
2.酒店安排【算法赛】 - 蓝桥云课
问题描述
第十六届蓝桥杯比赛太火爆了，赛场周围的酒店早早地就被抢订一空，剩下的房间寥寥无几。作为蓝桥学院的指导老师，小蓝为此头疼不已，因为他需要将同学们分配到不同的酒店去入住。
本次比赛中，小蓝带领了 M 名同学参赛。考场周围仅有 N 家酒店有空房，每家酒店的位置用 Ai 表示。酒店 i 和酒店 j 之间的距离为 ∣Ai−Aj∣。
每位同学将在其中一家酒店入住，每家酒店只容纳一名同学。由于比赛第二天时间紧迫，小蓝希望同学们早早集合赶往考场。集合时间取决于任意两名同学所住酒店之间的最大距离。现在小蓝想知道这个最大距离可能的最小值是多少。
作为同学中的一员，希望你能帮助指导老师小蓝解决这个问题。
输入格式
第一行输入两个整数 N,M (1 ≤ M ≤ N ≤ 10^5)，表示酒店的数量和同学的数量。
第二行输入 N 个整数 A1,A2,A3,…,AN (1 ≤ Ai ≤ 10^9)，表示每家酒店的位置。
输出格式
输出一个整数表示答案。
样例输入
5 3
1 2 4 5 6样例输出
2样例说明
当3位同学入住第1, 4, 5号酒店时为其中一种最优情况，答案为2。
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 512M |
| Java | 2s | 512M |
| Python3 | 3s | 512M |
| PyPy3 | 3s | 512M |
| Go | 3s | 512M |
| JavaScript | 3s | 512M |
总通过次数：384 | 总提交次数：780 | 通过率：40.2%
难度：中等 | 标签：思维，排序
思路：
有题目可以得知，这是一道二分题目，我们要枚举答案。我们通过案例就知道，当枚举的距离确定后，学生越少越容易满足枚举的答案，学生越多越容易不满足枚举的答案。所以我们可以画出一个图。
枚举每一个答案，寻找酒店之间是否有满足x的距离。注意，要m个酒店的寻找。
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int arr[N];
int n,m;
bool check(int x)
{for(int i = 1 ; i <= n-m+1 ; i++){if(arr[i+m-1] -arr[i] <= x)return true;}return false;
}
int main()
{cin >> n >> m;for(int i = 1 ; i <= n ; i++){cin >> arr[i];}sort(arr+1,arr+1+n);int l,r;l = -1, r = arr[n] - arr[1] + 1;while(l + 1 != r){int mid = (l + r) / 2;if(check(mid))r = mid;elsel = mid; }cout << r;return 0;
}