四、距离的智慧

题目描述

学校新建造了一个有 N（2≤N≤10^5) 个小隔间的自习室，这些隔间分布在一条直线上，坐标是x1x2x3…xn（0≤xi≤10^9）。为了保持尽可能的安静，减少周边环境的影响，睿智的大树老师想把自习学生安置在指定的隔间，所有自习学生中相邻两人的最近距离越大越好。有 C（2≤C≤N）名学生，那么，这个最大的最近距离是多少呢？

输入格式

第 1 行：两个用空格隔开的数字 N 和 C。

第 2∼ N+1 行：每行一个整数，表示每个隔间的坐标。

输出格式

输出只有一行，即相邻读者最大的最近距离。 输入输出样例

输入

5 3
1
2
8
4
9

输出

3

视频题解

https://dl.ccf.org.cn/video/videoDetail.html?_ack=1&id=7092424601733120

AC 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 10005;
int arr[MaxN] ;
int main() {
	int n,c;
	cin >> n >> c;
	for(int i = 1; i <= n; i++){
		cin >> arr[i];
	}
	sort(arr+1,arr+1+n); // 排序
	//二分查询
	int low = 0 , high = arr[n] - arr[1];
	int ans = 0 ; //最大的最近间隔
	int cnt = 1;
	while(low <= high){
		int left = 1;
		int mid = (low + high) / 2;

		for(int i= 2; i<=n;i++){
			if(arr[i] - arr[left] >= mid){
				cnt ++;
				left = i;
			}
		}
		if(cnt >= c){
			ans = max(ans,mid);
			low = mid + 1; // 左指针右移
		}else{
			high = mid -1; // 右指针左移
		}
	}
	cout << ans;
	
	return 0;
}