算法

(二分,贪心) $O(NlogL)$

如果长度 $Len$ 可以满足，那么当长度小于 $Len$ 时也可以满足，所以我们可以二分出最大的 $Len$。

剩下的问题是如何判断给定 $Len$ 的情况下，能否最多拿走 $M$ 块石头，使得所有相邻两块石头之间的距离不小于 $Len$。

这一步可以贪心来做。从前往后扫描每个石头：

• 如果当前石头和上一块石头的距离小于 $Len$，则当前石头必须拿走，否则最小距离就会小于 $Len$。
• 如果当前石头和上一块石头的距离大于等于 $Len$，则必然存在一个最优解，使得当前石头可以被拿走。证明：如果存在一个最优解跟我们的贪心解留下的石头不同，那么找出第一个不同的石头，我们把最优解中的留下石头换成贪心解中留下的石头，会发现仍然会得到一组合法方案，通过这种方式，可以逐步将最优解调整成贪心解，且留下的石头数不变，所以贪心解就是一组最优解。

扫描结束后判断拿走的石头数量是否小于等于 $M$。

时间复杂度分析

总共二分 $O(logL)$ 次，每次贪心的计算是 $O(N)$，因此总时间复杂度是 $O(NlogL)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50010;

int L, n, m;
int d[N];

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

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

    int l = 1, r = 1e9;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    printf("%d\n", r);
    return 0;
}