The Frog's Games

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;

}