codevs 3135 River Hopscotch

题目描述 Description

每年奶牛们举行一场奇异的活动。他们从左岸出发，一个个小心地跳过河上的石头，最后跳到右岸。左右岸上各有一块石头，为起点和终点，而它们之间有N(1<=N<=50000)块石头在河上，他们与两岸的两块石头处在一条直线上。左右岸相距L(1<=L<=1000000000)个单位长度，而每块石头到左岸都有一个距离Di（0<Di<L）.

Farmer John很自豪地看着他的奶牛们一个个跳过河，但是渐渐地厌倦了。他希望移走河上的一些石头，使得剩下的石头（包括岸上的）中，最近的两个石头间的距离增加。然而因为精力有限，使得他不能移走太多石头，最多移走M(0<=M<=N)块。

他想知道石头间的最短距离最长是多少。（好纠结的一句话）

输入描述 Input Description

第一行：三个空格分开的数：L,N,M

第二至第N+1行：每行一个整数，表示一块石头到左岸的距离。（绝对没有两块石头在同一位置）

输出描述 Output Description

仅仅一个整数：表示移走若干块石头后最长的最短距离（又绕了。。。。）。

样例输入 Sample Input

25 5 2

2

14

11

21

17

样例输出 Sample Output

4

数据范围及提示 Data Size & Hint

【样例说明】

移走距左岸2和14的石头

其他见题目

思路：

与codevs 4768 跳石头相同，都是二分答案。

代码:

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll a[50001],n,m,r,l;
int main()
{
    ll i,j;
    scanf("%lld%lld%lld",&r,&n,&m);
    for(i=1;i<=n;i++)
      scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    l=0;
    n++;
    a[n]=r;
    while(l<=r)
    {
        ll mid=(l+r)>>1,b=0,s=0;
        for(i=1;i<=n;i++)
        {
            if(a[i]-b<mid)
              s++;
            else
              b=a[i];
        }
        if(s>m)
          r=mid-1;
        else
          l=mid+1;
    }
    printf("%lld",l-1);
    return 0;
}