题目描述

每年奶牛们都会在一条笔直的河流上举办跳房子比赛。

比赛起点是一块岩石，终点是另一块岩石。

起点岩石和终点岩石之间的距离为 L
。

在起点和终点之间，有 N
 块岩石（不含起点和终点的岩石）。

每块岩石与起点岩石之间的距离为 Di
。

在比赛过程中，奶牛们将从起点岩石出发，在岩石之间跳跃，直至到达终点岩石。

为了提高比赛难度，约翰计划移除一些岩石，使得相距最近的两块岩石之间的距离尽可能大。

已知，约翰无法移除起点岩石和终点岩石，并且他最多只能移除 M
 块岩石。

请你计算，移除岩石后，相距最近的两块岩石之间的距离的最大可能值。

样例

25 5 2
2
14
11
21
17

4

算法1

(暴力枚举) $O(2^n)$

我最先想到的就是dfs暴搜, 但这种方法肯定过不了, 因为时间复杂度太高了~~~

算法2

(二分) $O(nlog2(l))$

定义l从最小距离开始, r到终点距离, 二分搜索, check函数判断需要移走多少块石头

时间复杂度

$O(n*log2(l))$

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50010;

int d[N];
int len, n, m;
int minl = INT32_MAX;

bool check(int x)
{
    int last = 0, cnt = 0;
    for (int i = 1; i <= n + 1; ++ i )
    {
        if (d[i] - d[last] < x)
        {
            if (++ cnt > m) return false;
        }
        else last = i;
    }
    return true;
}

int binary_search()
{
    for (int i = 1; i <= n + 1; ++ i )
        minl = min(minl, d[i] - d[i - 1]);

    int l = minl, r = len;
    while (l < r)
    {
        int mid = l + (r - l + 1) / 2;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    return r;
}

int main()
{
    scanf("%d%d%d", &len, &n, &m);
    for (int i = 1; i <= n; ++ i )
        scanf("%d", &d[i]);

    sort(d + 1, d + 1 + n);
    d[0] = 0, d[n + 1] = len;

    int res = binary_search();

    printf("%d", res);
    return 0;
}