【题目描述】

农夫 John 建造了一座很长的畜栏，它包括N(2<=N<100000)个隔间，这些小隔间依次编号为x1,x2,...xn(0<=xi<=1000000000)。但是，John的C(2<=C<=N)头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢?

【输入描述】

第一行：空格分隔的两个整数N和C；

第二行---第N+1行：i+1行指出了xi的位置。
N$N+$

【输出描述】

        一个整数，最大的最小值。

【样例输入】

5 3
1 2 8 4 9

【样例输出】

3

【提示】

    把牛放在1，4，8这样的最小距离是3。

【样例解释】

N=5,表示5个畜栏。C=3,表示3头牛。

把C头牛放到N个带有编号的隔间里，使得任意两头牛所在的隔间编号的最小差值最大。例如样例排完序后变成1 2 4 8 9，那么1位置放一头牛，4位置放一头牛，它们的差值为3；最后一头牛放在8或9位置都可以，和4位置的差值分别为4、5，和1位置的差值分别为7和8，不比3小，所以最大的最小值为3。

题目要保证两头牛的最小距离尽可能大，也就是畜栏的编号尽可能大。注意，牛没有编号，认为所有的牛都是一样的。

所以这道题目实际上是在说，从给定的编号中去选一堆编号，选编号的原则就是距离越大越好。

【题目分析】

• 最小值最大化问题(二分搜索)   
  

• 题目要求是把牛关到畜栏里面，而且题目保证牛的数量C比畜栏的数量小。

• 注意，题目中畜栏的编号不一定是有序的。

步骤：

C(d)：安排牛的位置使得最近的两头牛的距离不小于d

求满足C（d）最大的d。

C(d)可以安排牛的位置使得任意的牛之间的距离都不小于d

先对隔间编号从小到大排序，则最大距离不会超过两端的两头牛之间的差值，最小值为0。所以我们可以通过二分枚举最小值来求。假设当前的最小值为x，如果判断出最小差值为x时可以放下C头牛，说明当前的x有点小，就先让x变大再判断；如果放不下，说明当前的x太大了，就先让x变小然后再进行判断。直到求出一个最大的x就是最终的答案。

【参考答案】

#include<bits/stdc++.h> 
using namespace std;
int a[100005],n,c;
int judge(int mid)
{
    int i,count=1,t=a[0]; //count是指放了几头牛，从1开始。t用来表示当前的房间号
    for(i=1; i<n; i++)
    {
        if(a[i]-t>=mid)//判断两个房间之间的距离
        {
            count++;
            t=a[i];//修改t的值，即修改当前房间号，例如原来t=1,a[2]=4,若a[2]-t>=mid符合，那么t=4,然后算a[3]或者a[4]与t之间的距离。
            if(count>=c)//可以放下C头牛
                return 1;
        }
    }
    return 0;
}
int binary()//二分搜索符合条件的最小距离的最大值
{
    int low=0,high=a[n-1]-a[0],mid;
    while(low<=high)
    {
        mid=(low+high)/2;//mid即为最小房间号与最大房间号之间的距离
        if(judge(mid))
            low=mid+1;//所求距离>=mid，可以继续增大试探
        else
            high=mid-1;//所求距离<mid，所以必须减小来试探
    }
    return low-1; //由于在之前距离+1，所以此时-1
}
int main()
{
    while(scanf("%d%d",&n,&c))
    {
        int i;
        for(i=0; i<n; i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        printf("%d\n",binary());
    }
    return 0;
}