算法

(二分答案+贪心) $O(nlogL)$

寻找单调性：答案关于移动的石头个数单调。
移动的石头的个数越多，答案越大。

我们令$f(x)$表示，当最小距离不低于$x$时，最少移动多少块石头。
二分找出最后一个$f(x) \leqslant M$的$x$即为答案。

如何求$f(x)$？
一种贪心的策略是，从头开始，如果这一块石头与上一块石头的距离小于$x$，就直接把这一块石头移去。最后统计移去的石头的总个数。关于证明可以用反证法来证明。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    int l, n, m;
    cin >> l >> n >> m;

    vector<int> d(n+1);
    rep(i, n) cin >> d[i];
    d[n] = l;

    int ac = -1, wa = l+1;
    while (abs(ac-wa) > 1) {
        int wj = (ac+wa)/2;

        auto ok = [&]{
            int cnt = 0, last = 0;
            rep(i, n+1) {
                if (d[i]-last < wj) cnt++;
                else last = d[i];
            }
            return cnt <= m;
        }();

        (ok ? ac : wa) = wj;
    }

    cout << ac << '\n';

    return 0;
}