思路:
1. 主要要搞清楚二分的什么东西,其实二分就是满足“条件”的两个牛舍之间的最大值
2. “条件”是指n个牛舍,要在间隔为>=x(二分的就是这个东西)的情况下,装下m头牛
3. 显然,当x较小的时候,肯定满足条件,但我们要找的是最大值,x越大,才越接近答案
4. 为什么说是又说是最小值,因为相邻的两个牛舍之间的距离要取min
5. 所以我们二分的时候是要枚举当距离是x的时候所选牛舍之间的距离是否合法
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n, m;
bool check(int x)
{
int pre = a[0]; //表示将1头牛放进第一个牛舍中
int sum = 1; //记录牛舍中已经放了几头牛
//枚举剩余的牛舍,看间隔为x的情况下,能否放入上下的m-1头牛
for(int i = 1; i < n; i ++ )
{
if(a[i] - pre >= x)
{
sum ++;
pre = a[i]; //更新当前放过牛的牛舍下标
}
}
//能放下
if(sum >= m) return true;
else return false;
}
int main()
{
cin >> n >> m;
//读入所有牛舍的位置
for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
sort(a, a + n);
int l = 0, r = 1e9; //二分出来最大的最小值,即牛舍之间的距离的最大最小值
while(l < r)
{
int mid = l + r + 1 >> 1;
//检查一下当这m个牛舍的距离是mid的时候,能否放下这m头牛。
//在能放下这m头牛的情况下,尽可能使得mid最大,因此当mid=0,1较小数的时候一定放的下这m头牛
//将牛舍距离从小到大二分答案,相当于在很多可行方案中取右端点
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << l << endl;
return 0;
}