题目描述

农夫约翰建造了一座有 n
间牛舍的小屋，牛舍排在一条直线上，第 i
间牛舍在 xi
的位置，但是约翰的 m
头牛对小屋很不满意，因此经常互相攻击。

约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。

也就是要最大化最近的两头牛之间的距离。

牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。

为了不让牛互相伤害。

约翰决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？

输入格式
第一行用空格分隔的两个整数 n
和 m
；

第二行为 n
个用空格隔开的整数，表示位置 xi。

输出格式
输出仅一个整数，表示最大的最小距离值。

样例输入

5 3
1 2 8 4 9

样例输出

3

算法1

二分查找

C++ 代码

#include<iostream>
#include<climits>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,m,x[N];

//对这个最小距离进行判断看成不成立，如果能满足直接返回true
bool Check(int dst)
{
    //贪心思路
    int count=1;
    int pastx=x[1];
    for(int i=2;i<=n;i++)
    {
        //当前位置是否能放牛
        if(x[i]-pastx>=dst)
        {
            count++;
            pastx=x[i];
        }
        //如果牛放满了说明成立
        if(count==m)return true;
    }
    return false;
}

int main()
{
    //输入牛棚数量和牛的头数
    cin>>n>>m;
    //第i个牛棚在哪个位置
    for(int i=1;i<=n;i++) cin>>x[i];

    //对牛棚排序
    sort(x+1,x+n+1);
    //确定二分边界
    int l=1,r=x[n]-x[1];
    while(l<=r)
    {
        int mid=(r+l)/2;
        //满足Check说明满足，说明还能更大
        if(Check(mid)) l=mid+1;
        //向下取整
        else r=mid-1;

    }
    cout<<r<<endl;
    return 0;
}