The Frog's Games

﹏ヽ暗。殇╰゛Y 2022-05-28 02:07 95阅读 0赞

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

Sample Output：

思路：这题主要用到了二分查找的应用。我们将石头之间与石头和河岸的距离存储在数组中，然后用二分查找的方法去查询，在限制的步数中，青蛙能够跳的最远的距离。

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;  
\}