HLG 1584 青蛙過河 （二分）

Description
青蛙王國一年一度的游戲又開始了，這個游戲要求青蛙必須跳過河。河的寬度是 L 。河裡有n塊石頭，這n塊石頭從河的一邊筆直的連到另一邊。青蛙只能踩著石頭過河，如果它們掉到水裡，將被淘汰出局。游戲規定青蛙最多跳m次。現在青蛙想要知道如果在這m步內跳到岸的那邊，它一步最長需要跳多長。

Input
輸入包括多組測試結果。

第一行輸入三個數字L(1<= L <= 1000 000 000),n(0<= n <= 500000),m(1<= m <= n+1)。

接下來一行有n個用空格隔開的整數，表示每塊石頭到跳躍起點的距離，兩塊石頭不可能同時出現在一個地方。

Output

對於每次測試，輸出一個整數表示青蛙至少應該有的最大的能力，即為一步最多能跳多長，每步實際跳的長度一定小於等於這個最小的最大能力。

Sample Input

6 1 2

2

25 3 3

11 2 18

Sample Output
4

11

代碼如下：

#include 
#include 
#include 
#include 
#include 
#define MAXN 500000+10
#define RST(N)memset(N, 0, sizeof(N))
using namespace std;

int l, m, n, a[500005];

int jump(int s)
{
    int point = 0, i = 0;
    int sum = 0;
    for( ; i<=n; i++) {
        if(a[i] > point+s) {
            point=a[i-1];
            sum++, i--;
        }
        if(sum == m) return 0;
    }
    return 1;
}

int main()
{
    while(~scanf(%d %d %d, &l, &n, &m)) {
        for(int i=0; i left) {
            mid = (right+left) >> 1;
            if(jump(mid)) right = mid;
            else left = mid + 1;
        }
        printf(%d
, right);
    }
    return 0;
}