题目链接：https://vjudge.net/problem/POJ-3258

题意：

有一条河长为L，河中间有n块石头，算上开始和结尾一共n+2个，现在问去掉m块石头，问最短距离中的最大值是多少？

分析：

二分寻找一个值，使得可以移除m个石头。

code：

// #include <bits/stdc++.h>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 5e4 + 7;
const int INF = 0X3F3F3F3F; 

int a[MAXN];    // 存石头的位置

int main()
{
    int l, n, m;
    while(scanf("%d %d %d", &l, &n, &m) != EOF)
    {
        int low = l;    // 二分左右边界
        int high = l;
        a[0] = 0;
        a[n+1] = l;
        for(int i=1; i<=n; i++)
        {
            scanf("%d", &a[i]);
            low = min(low, a[i] - a[i-1]);  // 更新左边界，找到起始的最小左边界
        }
        low = min(low, a[n+1] - a[n]);
        sort(a, a+n+2);     // 输入无序，排为升序

        while(low <= high)
        {
            int mid = (low+high) / 2;
            int sum = 0;
            int cnt = 0;
            int i = 1;
            while(i <= n+1)  // 从第一个点遍历到最后一个点，终点
            {
                sum += a[i] - a[i-1];  // 两块石头之间的距离，不一定是连续的
                if(sum <= mid)
                {
                    cnt ++;
                    i++;
                }
                else
                {
                    sum = 0;
                    i++;
                }
            }
             // cnt == m, 说明当前mid的值已经可以移除m个石头
             // 但是当前mid还不是可能最小值，有可能mid+1也符合条件
            //  我们找的是最小值中的最大值，而不是最小值中的最小值，所以左边界应该+1
            if(cnt <= m)   
                low = mid + 1;
            else
                high = mid - 1;
        }
        printf("%d\n", low);

    }


    return 0;
}