Description

Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, straight river with a rock at the start and another rock at the end, L units away from the start (1 ≤ L ≤ 1,000,000,000). Along the river between the starting and ending rocks, N (0 ≤ N ≤ 50,000) more rocks appear, each at an integral distance D_i from the start (0 < D_i < L).

To play the game, each cow in turn starts at the starting rock and tries to reach the finish at the ending rock, jumping only from rock to rock. Of course, less agile cows never make it to the final rock, ending up instead in the river.

Farmer John is PRoud of his cows and watches this event each year. But as time goes by, he tires of watching the timid cows of the other farmers limp across the short distances between rocks placed too closely together. He plans to remove several rocks in order to increase the shortest distance a cow will have to jump to reach the end. He knows he cannot remove the starting and ending rocks, but he calculates that he has enough resources to remove up to M rocks (0 ≤ M ≤ N).

FJ wants to know exactly how much he can increase the shortest distance *before* he starts removing the rocks. Help Farmer John determine the greatest possible shortest distance a cow has to jump after removing the optimal set of M rocks.

Input

Output

Sample Input

25 5 2214112117
Sample Output
4
Hint
Before removing any rocks, the shortest jump was a jump of 2 from 0 (the start) to 2. After removing the rocks at 2 and 14, the shortest required jump is a jump of 4 (from 17 to 21 or from 21 to 25).
Source
USACO 2006 December Silver
題目意思：
從起點到終點，即0到L這段路程中有N塊石頭，奶牛每次只能從前一塊跳到后一塊石頭上去。想要移除除了起點終點之外的M塊石頭，使得奶牛從起點到終點跳躍的最短距離最大。
解題思路：
添加起終點的石頭0和L。對移除的石頭個數(shù)二分，low是奶牛從起點到終點跳躍的最短距離，high是整個路程L。①枚舉各個石頭，計算其與前一塊石頭之間的距離，然后相加起來：如果比最短距離小，說明距離短了，可以移除當前石頭來增大距離，移除的石頭數(shù)量加1；否則說明距離夠大，置零后重新計算下一段距離。②枚舉完畢后：如果移除的石頭數(shù)量大于M，說明距離偏大，范圍變成前二分之一；否則說明距離偏小，范圍變成后二分之一。
#include<iostream>#include<cstdio>#include<iomanip>#include<cmath>#include<cstdlib>#include<cstring>#include<map>#include<algorithm>using namespace std;#define INF 0xfffffff#define MAXN 50050int a[MAXN];int l,n,m,high,low,mid;bool solve(){    int res=0,sum=0;    for(int i=1; i<=n+1; ++i)    {        int t=a[i]-a[i-1];//與前一塊石頭之間的距離        sum+=t;//若干塊距離之和        if(sum<=mid) ++res;        else sum=0;    }    if(res<=m) return true;    else return false;}int main(){#ifdef ONLINE_JUDGE#else    freopen("F:/cb/read.txt","r",stdin);    //freopen("F:/cb/out.txt","w",stdout);#endif    ios::sync_with_stdio(false);    cin.tie(0);    cin>>l>>n>>m;    high=l,low=l;    a[0]=0;    a[n+1]=l;    for(int i=0; i<=n; ++i)        cin>>a[i];    sort(a,a+n+2);    for(int i=1; i<=n+1; ++i)    {        int t=a[i]-a[i-1];//與前一塊石頭之間的距離        if(t<low) low=t;    }    while(low<=high)    {        mid=0.5*(low+high);        if(solve()) low=mid+1;        else high=mid-1;    }    cout<<low<<endl;    return 0;}/*25 5 2214112117*/