题目描述

Farmer John 建造了一个有 NN(2≤ N ≤ 100000) 个隔间的牛棚，这些隔间分布在一条直线上，坐标是 x1，，，，xn（0≤xi≤1000000000）。

他的 C(2≤C≤ N) 头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗，Farmer John 想把这些牛安置在指定的隔间，所有牛中相邻两头的最近距离越大越好。那么，这个最大的最近距离是多少呢？

输入格式：

第 11 行：两个用空格隔开的数字 NN 和 CC。

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

输出格式：

输出只有一行，即相邻两头牛最大的最近距离。

输入输出样例

输入：

5 3

1

2

8

4

9

输出：

3

分析：

这道题很是经典，二分法，尽管我不是很会。

类似的最大值最小化或者最小值最大化问题，通常用二分法就可以很好地解决。我们定义：

设 C(d)表示可以安排瓶盖的位置使得最近的两个瓶盖的距离不小于 d

那么问题就变成了求满足 C(d)的最大的 d，另外，最近的间距不小于 d 也可以说成是所有瓶盖的间距都不小于 d，因此就有 C(d)表示可以安排瓶盖的位置使得任意的两个瓶盖的距离不小于 d。

这个问题的判断使用贪心法便可非常容易地求解。

1.对瓶盖的位置 x 进行排序
2.把第一个瓶盖放入 x0 的位置
3.如果第 i 个瓶盖放入了 xj 的话，第 i+1 个瓶盖就要放入满足 xj+d≤xk 的最小的 xk 中

对 x 的排序只需在最开始时进行一次就可以了，每一次判断对每个瓶盖最多进行一次处理，因此时间复杂度是 O(nlogn)

代码如下：

include<bits/stdc++.h>

using namespace std;

int a,b,l,r,mid;

int A[1000001];

inline bool check(int x)

{

int rgt=A[1]+x;
int sum=1;
for(int i=2;i<=a;i++)
{
if(A[i]>=rgt)
    {
        sum++;
        rgt=A[i]+x;
    }
}
return sum>=b;

}

int main()

{

cin>>a>>b;
for(int i=1;i<=a;i++)
cin>>A[i];
sort(A+1,A+1+a);
l=0,r=A[a]-A[1];
while(l<=r)
{
    mid=(l+r)/2;
if(check(mid))l=mid+1;
else r=mid-1;
}
cout<<r<<endl;
return 0;

}

要好好的看看，