难度：普及/提高-

题目描述

        陶陶是个贪玩的孩子，他在地上丢了A个瓶盖，为了简化问题，我们可以当作这A个瓶盖丢在一条直线上，现在他想从这些瓶盖里找出B个，使得距离最近的2个距离最大，他想知道，最大可以到多少呢？

输入输出格式

输入格式:

        第一行，两个整数，A，B。(B≤A≤100000)
        第二行，A个整数，分别为这A个瓶盖坐标。

输出格式:

        仅一个整数，为所求答案。

输入输出样例

Sample input

5 3
1 2 3 4 5

Sample output

2

题解

        本题是一道典型的二分答案题目。考察二分和贪心思想。
        二分答案是一种寻求答案的方法，其原理利用了答案的单调性。在给定的答案域中，判断中点答案的可行性，根据其可行性再在答案域的左半区间或右半区间寻求答案，直到找到最终答案。
        为了解释地更加清晰，下面说明几个概念。

  • 答案域：答案可能的取值区间。在本题中答案域的左值为当前最小距离，最大值为最末与最初瓶盖坐标的差值。
  • 可行：当存在一种方案使得在取出不小于B个瓶盖时，可以使任意两个相邻瓶盖间距都大于或等于x，则称x是可行的。也就是说，存在一种符合题目要求的选取策略，使得瓶盖间距最小值大于或等于x。同样，当不存在任何一种方案使得上述条件成立，则称x不可行。
  • 答案单调性：当一个x可行时，由于要求最大值，故正确答案一定大于或等于x;类似地，当x不可行时，易知所有大于x的值都不可行，正确答案一定小于x。这就是答案的单调性。

        根据以上说明，用二分查找方法，判定中点值的可行性，从而缩小区间，确定答案。
        判定一个值可行性的方法可用贪心策略，详见代码。
        值得注意的是，本题中并未说明输入数据有序，必须先对输入的数据进行排序，再二分答案。

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
#include<iostream>
#include<algorithm>

using namespace std;
int op[100005], a, b;

int check(int x) {
    int p = op[1], q = a - b;
    for (register int i = 2; i <= a; i++) {
        if (op[i] - p < x) {
            if (!q)return 0;
            q--;
        } else p = op[i];
    }
    return 1;
}

int find(int l, int r)//[,)
{
    if (r == l + 1)return l;
    int mid = (l + r) / 2;
    if (check(mid))return find(mid, r);
    else return find(l, mid);
}

int main() {
    cin >> a >> b;
    int minn = 1e8;
    for (register int i = 1; i <= a; i++)cin >> op[i];
    sort(op + 1, op + a + 1);
    for (register int i = 2; i <= a; i++)minn = min(minn, op[i] - op[i - 1]);
    cout << find(minn, op[a] - op[1]);
    return 0;
}