http://acm.hdu.edu.cn/showproblem.php?pid=4004
题意:青蛙过长L的河,只能落在石头上,石头数量是n,给出n个坐标,至多跳m次,求在可以过河的条件下,青蛙跳的最大距离的最小值
水题,二分答案即可,验证的时候青蛙显然应尽可能落在远端
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <set> using namespace std; int L,n,m;
int a[]; int OK(int x){
int now=;
if(x>=L)return ;
if(n>= && x>=a[n-]){
if(x>=L-a[n-] && m>=)return ;
return ;
}
int cnt=;
for(int i=;i<n-;i++){
if(now+x>=a[i] && now+x<a[i+]){
now=a[i];
cnt++;
}
}
if(now+x>=L){
cnt++;
if(cnt<=m)return ;
return ;
}
if(now+x>=a[n-]){
cnt++;
now=a[n-];
if(now+x>=L){
cnt++;
if(cnt<=m)return ;
return ;
}
else return ;
}
return ;
} int main(){
while(~scanf("%d%d%d",&L,&n,&m)){
for(int i=;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
int l,r;
l=;r=;
while(r-l>=){
int mid=(l+r)>>;
if(OK(mid))r=mid;
else l=mid;
}
for(int i=l;i<=r;i++){
if(OK(i)){
printf("%d\n",i);
break;
}
}
}
return ;
}