二分答案

分析：和雨巨讲的牛棚放牛类似，这题可以把要移走的石头看成空牛棚，留下的石头看成要跳的石头，然后开始二分答案，假设最短距离中的最长距离是x，那么枚举每块石头的距离，小于这个x的话则这块石头要去掉，然后记录下要去掉的石头数cnt，如果超过了m，说明距离大了，让r=mid - 1，否则距离小了，让l = mid + 1。一直这样下去可以得到最终答案ans。

#include <bits/stdc++.h>
#include <iostream>
const int Max = 100 * 100 * 100 + 5;
#define LL long long
const int mod = 1e9+7;
//const int inx = INT_MAX; 
using namespace std;
//    srand(time(NULL));
//        m = rand() % 1000 + 1;

//定义i i(A) i+n i+n(B) i+n+n i+n+n(C) 
//bitset<Max>s,q;

int a[50005],n,m;

bool pd(int x)
{
    int t = 0,cn = 0;
    for(int i = 1; i <= n; i++){
        if(a[i] - t < x)
            cn++;
        else 
            t = a[i]; 
    }
    if(cn > m) return false;
    return true;
}

int main()
{ 
    int r,l,L,i,j,ans,mid;
    cin >> L >> n >> m;
    for(i = 1; i <= n; i++) cin >> a[i];
    n++;
    a[n] = L;
    l = 0,r = L;
    while(l <= r){
        mid = (r + l) / 2;
        if(pd(mid)){
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << ans;
    return 0;
}