农夫约翰建造了一座有$n$间牛舍的小屋，牛舍排在一条直线上，第$i$间牛舍在$xi$的位置，但是约翰的$m$头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。

牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。John 决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？

输入格式:

第一行用空格分隔的两个整数$n$和$m$，$n$，$m$<=105；

第二行为$n$个用空格隔开的整数，表示位置$x_i$。$x_{i}$<$MAXINT$

输出格式:

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

输入样例:

1
2
5 3
1 2 8 4 9

输出样例:

1
3

题解

  • 这是一个二分答案的题目，二分答案主要是关键在答案，我们二分搜索是搜索的答案。如果说当前这个mid符合题目要求，那么可以尝试扩大答案，如果不符合要求可以缩小，直到找到符合和恰好不符合的边界值，那么最终结果是会可以得到最优的。
  • 下题是尝试每个间隔中，如果使用这个间隔，正好能给牛分配好，则符合条件，扩大范围，然后继续二分搜索符合题意的答案。最后输出结果即可。
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
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    static StreamTokenizer st = new StreamTokenizer(new InputStreamReader(System.in));

    static int nextInt() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }

    // 标记已经有了的
    static int m;
    static int[] arr;
    static int n;

    public static void main(String[] args) throws IOException {
        n = nextInt();
        m = nextInt();
        arr = new int[n];

        for (int i = 0; i < n; i++) arr[i] = nextInt();
        // 先排序
        Arrays.sort(arr);
        int l = 0; // 左
        int r = arr[n - 1] - arr[0];
        while (l <= r) {
            int mid = (l + r) >>> 1;// 中
            if (checkDistance(mid)) {
                l = mid +1;
            }else {
                r = mid -1;
            }

        }
        pw.println(r);
        pw.close();
    }

    static boolean checkDistance(int d) {
        int last = d + arr[0];
        int sum = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i] < last) continue;
            last = arr[i] + d;
            sum++;
        }
        return sum >= m;
    }


}