题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4004
大致题意 二分最大跳跃能力,判断是否可以在m次内到达对岸!
分析:由于求青蛙最小弹跳能力,所以二分不断枚举能力x,再对x判断是否在m次内到达对岸。。。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define inf 1<<30
using namespace std; int n,m,l,a[];
int judge(int x)
{
int res=,temp=;
for(int i=;i<=n;i++)
{
if(a[i]-temp>x)return ;
while(a[i]-temp<=x&&i<=n)i++;
temp=a[i-];i--;
res++;
}
return res<=m;
}
int main()
{
while(scanf("%d%d%d",&l,&n,&m)>)
{
for(int i=;i<=n;i++)scanf("%d",&a[i]);
a[++n]=l;
sort(a+,a+n+);
int left=,right=l,mid,ans;
while(left<=right)
{
mid=(left+right)/;
if(judge(mid))
right=mid-,ans=mid;
else left=mid+;
}
printf("%d\n",ans);
}
}