为了弥补自己的二分太渣，从二分的水题做起，从我做起~

题目描述

 

农夫约翰建造了一座有n间牛舍的小屋，牛舍排在一条直线上，第i间牛舍在xi的位置，但是约翰的m头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。
牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？

 

输入

第一行用空格分隔的两个整数n和m；
第二行为n个用空格隔开的整数，表示位置xi。

 

输出

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

 

样例输入

复制样例数据

5 3
1 2 8 4 9

样例输出

3

 

提示

把牛放在1,4,8这样最小距离是3

2≤n≤105 , 0≤xi≤109, 2≤m≤n

之前做过一个题目与之类似:是跳石头这里链接

方法都一样我们每次枚举一个x判断它为 最小距离是否可行，如果可行我们保留到一个集合里，然后选出最大的可行值就是答案，不可行直接跳过，这种方法绝对可以筛选是没有问题的，答案也绝对是对的，但是复杂度太高 (稳TLE)，所以还是二分，以后碰见最大最小值，最小最大值基本都是二分。

这里需要注意几个细节：

1.数据的范围：1e9出现警告 long long 安排上。

2.可行条件是，在这个距离下可以安放m头牛及包括m，但是第一头已经安排上了，所以条件为 tot>=2,tot为计数器。

 

然后代码附上：

#include <queue>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#define MIN(x,y) ((x)<(y)?(x) : (y))
#define MAX(x,y) ((x)>(y)?(x) : (y))
#define rl(a) scanf("%d",&a);
#include <sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod=10007;
const int INF=1e9;
const int maxn=1e6+5;
ll a[maxn];
int n,m;
bool judge(int x)
{
    ll now=a[1];
    ll tot=1;
    for(ll i=2;i<=n;i++)
    {
        if(a[i]-now>=x)
        {
            now=a[i];
            tot++;
        }
    }
    if(tot>=m) return true;//我们在判断时，已经假设第一头已经放了。
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    sort(a+1,a+1+n);//不要忘记排序。
    ll l=0,r=a[n]-a[1];
    ll ans;
    while(l<=r)
    {
        ll mid=(l+r)/2;
        if(judge(mid)==true)
        {
            l=mid+1;
            ans=mid;
        }
        else
            r=mid-1;
    }
    printf("%lld\n",ans);
    return 0;
}