学步园

这题是求一个最大的最短距离。

如果遍历的把每一段距离都求出来……然后再暴力得比较的话，可能会超时吧。。。

然后既然是二分的训练……那就只好用二分了。

二分，把起点位置作为左端点，把总长度，也就是终点作为右端点。当然一开始要把rock数组排序。

一开始想过要不把每个距离都求出来然后再排序。。。然后开了个fuck数组。。。其实是不行的。。。因为这些石头都是有原始顺序的，它们之间的距离都是有一定顺序的，打乱排序之后去掉那个石头是不好判断的……

所以就用二分，然后有个判断的ok函数。

想法是 假设我从头开始删石头，每删一个石头就会有两个距离连起来，将这个距离和二分的mid进行比较，直到比mid大了就将计算距离的sum清零，重新计数，这样的话，就能求出某个mid对应的，需要去除的石头的个数、如果这个个数大于M，那么就是说要去除的太多了，那么就需要降上限，反之，就需要提升下限……

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

using namespace std;

int L,N,M,l,r,mid;
int rock[50005];

bool ok(int m)
{
    int tem=0;// 记录有几个石头是可以去掉的
    int sum=0;
    for(int i=1;i<=N+1;++i)
    {
        sum+= rock[i]-rock[i-1];// 累加相邻的两个石头之间的距离，累加之后判断与m的大小
        if( sum <= m)//如果sum 小于等于m，就说明还可以再去点石头，使得最短距离为m
        {
            tem++;
        }
        else//如果大于m了，那就不用再去除石头了，将sum清零，重新计算。
        {
            sum=0;
        }
    }
    return tem <= M;
}

int solve()
{
    l = 1;
    r = L;
    while(l <=r)
    {
        mid = (l+r)/2;
        if(ok(mid))// 如果tem小于M了， 说明要去除的石头少了了，那么l就要向右移动。反之，r向左移动。
            l = mid+1;
        else
            r = mid-1;
    }
    return l;
}

int main()
{
    scanf("%d%d%d",&L,&N,&M);
    for(int i = 1;i<=N;++i)
    {
        scanf("%d",&rock[i]);
    }
    rock[0] = 0;//起点的那个石头
    rock[N+1] = L;//终点的那个石头
    sort(rock,rock+N+2);

    printf("%d\n",solve());

    return 0;
}