POJ3258 River Hopscotch 二分 java

解法：二分

就像用二分法解方程的解一样，不断的二分，直到满足条件

package gxyz1;

import java.util.Arrays;
import java.util.Scanner;

public class B {
	public static int[] arr;
	public static int L,M,N;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		 L = sc.nextInt();
		 N = sc.nextInt();
		 M = sc.nextInt();
		arr = new int[N+1];
		for (int i = 1; i <= N; i++) {
			arr[i] = sc.nextInt();
		}
		int ans = 0;
		Arrays.sort(arr);
		int left = 0,right=L;
		while(right>=left) {
			int mid = (left+right)/2;
			if(fun(mid)) {
				left = mid +1;
				ans = mid;
			}else {
				right = mid - 1;
			}
		}
		System.out.println(ans);
		
	}
	private static boolean fun(int mid) {

		int start=0,x=0;//用start表示每次落脚点的坐标，每落一次地更新一次start 
		for(int i=1;i<=N;i++)
		{
			if(arr[i]-start<mid)  //这里主要用来判断下一块石头跳与不跳
			x++;//x表示去掉的石头数，如果mid大于要跳的距离，就跳过当前这个石头，此时x++ ，并且不落地 
			else
			start=arr[i];//此时落地！ 
		}
		if(L-start<mid)//判断最后一跳跳的距离要是小于mid的话那是不可以的 ，因为以mid为最小距离不可能跳到最后一块
		return false;
		if(x>M)//要是x>m就说明最小距离mid太大啦 
		return false;
		return true;
	}

}