Problem  Description：

青蛙王国的年度游戏再次开始。最着名的比赛是铁蛙铁人三项。Ironfrog Triathlon的一项测试正在跳跃。这个项目需要青蛙运动员跳过河。河的宽度是L（1 <= L <= 1000000000）。有n（0 <= n <= 500000）块石头从河岸的一边直线排列成直线。青蛙只能跳过河，但他们可以登陆石头。如果他们掉进河里，他们

就出去了。要求青蛙最多跳m（1 <= m <= n + 1）次。现在青蛙想知道他们是否想跳过河，至少他们应该具备什么能力。（这是青蛙最长的跳跃距离）。

Input：

输入包含几种情况。每种情况的第一行包含三个正整数L，n和m。然后n行。每个代表从开始的银行到第n块石头的距离，两块石头出现在一个地方是不可能的。

Output：

对于每种情况，至少应该输出一个表示青蛙能力的整数。

Sample  Input：

6 1 2
2
25 3 3
11 
2

18

Sample  Output：

4

11

思路：这题主要用到了二分查找的应用。我们将石头之间与石头和河岸的距离存储在数组中，然后用二分查找的方法去查询，在限制的步数中，青蛙能够跳的最远的距离。

My  DaiMa：

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int judge(int n,int m,int a[],int t)
{
    int i,j=0,k=0;
    for(i=1;i<n;i++)
    {
        if(a[i]-a[j]<=m&&a[i+1]-a[j]>m)
        {
            k++;  //统计跳的次数
            j=i;  //更新起点
        }
    }
    k++;
    if(k<=t)
        return 1;
    else
        return 0;
}
int main()
{
    int L,n,m,i,a[500002];
    while(~scanf("%d%d%d",&L,&n,&m))
    {
        int low,high,b,mid;
        a[0]=0;a[n+1]=L;
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n+1);
        int ma=0;
        for(i=1;i<=n+1;i++)
        {
            if(a[i]-a[i-1]>ma)
                ma=a[i]-a[i-1];  //石头和石头之间的最远距离
        }
        low=ma;
        high=L;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(judge(n+1,mid,a,m))
            {
                b=mid;
                high=mid-1;
            }
            else
                low=mid+1;
        }
        cout<<b<<endl;
    }
    return 0;
}