题目描述

Farmer John 建造了一个有 N$(2 ≤ N ≤ 100000) $个隔间的牛棚，这些隔间分布在一条直线上，坐标是 x1,...,xN(0≤xi≤1000000000)x_1 ,...,x_N (0 ≤ x_i ≤ 1000000000)。

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

输入格式

第 1 行：两个用空格隔开的数字 N和 C。

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

输出格式

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

代码编写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>

using namespace std;

// N个隔间, 2<=N<=100000
int N;
// C头牛，2<=C<=N<=100000
int C;
// 牛棚坐标
int x[100001];


// 判定当两头牛之间的距离不得小于d时，是否满足题意
bool judge(int d){
    // 记录上一只牛的位置，起始位置即第一个牛棚
    int lastCowPos = x[1];
    // 剩余需要安放的牛数目
    int remainCowCount = C - 1;
    
    // 遍历剩下的每个牛棚
    for(int i=2;i<=N;i++){
        // 若当前牛棚距离上一个牛距离小于d，不得在此处安放牛
        if(x[i] - lastCowPos>=d){
            // 可以在此处安放一头牛
            remainCowCount--;
            // 更新上一头牛的位置
            lastCowPos = x[i];
        }

        // 若牛被安排完了，那就是满足满足题目了
        if(remainCowCount <= 0){
            return true;
        }
    }
    // 还没被安排完，不满足题目
    return false;
}

int main(){
    cin>>N>>C;
    for(int i=1;i<=N;i++) cin>>x[i];
    sort(x+1,x+1+N);
    // 最小距离的上界，极限情况为C==N时，最大的最小距离为1
    int l = 1;
    // 最小距离的下界，极限情况为C==2时，最大的最小距离为x[N]-x[1]
    int r = x[N] - x[1];

    // 二分搜索一个最大的最近距离    
    // 若judge(m) == true, 则说明安排两头牛的距离不小于m是可行的
    // 此时若减小m, 必定还是可行的
    // 此时若增大m, 两牛之间最短距离增大，则牛棚可能会不够用，
    // 故需要寻找一个临界值，使得m尽可能大，而又要不能使牛棚不够用
    // 即能够寻找一个最大的最近距离
    while (l<=r)
    {
        int mid = (l+r) / 2;
        
        if(judge(mid)){
            // 左边界移动到中间+1
            l = mid+1;
        }else{
            r = mid - 1;
        }
    }
    cout<<r<<endl;
    return 0;
}