The Frog's Games

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65768/65768K (Java/Other)
Total Submission(s) : 12   Accepted Submission(s) : 5

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

The annual Games in frogs' kingdom started again. The most famous game is the Ironfrog Triathlon. One test in the Ironfrog Triathlon is jumping. This project requires the frog athletes to jump over the river. The width of the river is L (1<= L <= 1000000000). There are n (0<= n <= 500000) stones lined up in a straight line from one side to the other side of the river. The frogs can only jump through the river, but they can land on the stones. If they fall into the river, they
are out. The frogs was asked to jump at most m (1<= m <= n+1) times. Now the frogs want to know if they want to jump across the river, at least what ability should they have. (That is the frog's longest jump distance).

Input

The input contains several cases. The first line of each case contains three positive integer L, n, and m.
Then n lines follow. Each stands for the distance from the starting banks to the nth stone, two stone appear in one place is impossible.

Output

For each case, output a integer standing for the frog's ability at least they should have.

Sample Input

6 1 2
2
25 3 3
11 
2
18

Sample Output

4
11

Source

The 36th ACM/ICPC Asia Regional Dalian Site —— Online Contest 



思路：
题意大体就是， 有一条长度为L的河流，中间穿插n个石凳，青蛙跳m次经过石凳后到达对岸，求在保证青蛙能完成过河的情况下每次跳跃的最大距离的最小值。这道题就是在一个范围内找一个最小数，因为朴素的算法对数据量很大的题目会TLE，所以这里采用二分的思想。首先输入的是石头，这里先加上两块石头，一块是最初的0，另一块是最终的l，所以现在就有n+1块石头来跳。然后排序，组成路径。首要要遍历一遍，找出相邻石头间距的最大值maxn，这也是我们一会查找时候的最初左端点（）。接下来就是在maxn~l（跳跃能力）区间里找那个能够在m次内跳过河的能力的最小值。然后就对定义一个函数f是用来求当跳跃的能力值是x的时候跳越过河最少需要多少步。每次询问中点值表示的能力能不能过河，如果能，就往左半边区间内去找更小的，如果不能就右半边区间找。这里的一个WA点就是在把mid赋值给left或者right的时候，不能原封不动的把mid赋值，而是要±1...


代码： 
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

int a[500000+5];
int n;

int f(int x)
{
	int i=0,j,num=0;
	while(i<n)
	{
	  for(j=i+1;j<=n;j++)
	  {
	      if(a[j]-a[i]>x) 
		  {
		     num++;break;
		  }
	  }
	  i=j-1;
	 }
	 return num+1;
}

int main()
{
	//freopen("in.txt","r",stdin);
	int l,m;
	while(scanf("%d%d%d",&l,&n,&m)!=EOF)
	{
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
		}
		a[0]=0;
		a[n+1]=l;
		sort(a,a+n+1);
		n=n+1;
		int left=0,right=l;
		for(int i=0;i<n;i++)
		{
			int maxn=a[i+1]-a[i];
			if(maxn>left)left=maxn;
		}
		while(left<=right)
		{
			int mid=(left+right)/2;
			int ans=f(mid);
			if(ans>m)
			{
				left=mid;
			}
			else right=mid;
		}
		printf("%d\n",left);
	}
	return 0;
}