Saruman's Army(PKU No.3069)

Saruman's Army(PKU No.3069)

N個の点が直線状にある。点iの位置は。N個のうちいくつかの点を選び、それらの点に印をつける。N個の全ての点について、距離がＲ以内の場所に印をつけられた点がなければならない。条件を満たす、印をつけた点の最小の個数を求める。
制約

アルゴリズム

カバーされていない最も左の点からからR以内にある最も右の点に印をつける貪欲法。最も左の点から単に2R以内のものをカバーできるとは限らないことに注意(最も左の点+Rの地点に点があるとは限らない)。
C++ならstd::upper_boundを使って簡単に記述できる。

コード

import java.util.*;
public class pku3069 {
	static Scanner scanner;
	public static void main(String[] args) {
		scanner = new Scanner(System.in);
		new pku3069();
	}
	pku3069(){
		while(true){
			int R = scanner.nextInt();
			int N = scanner.nextInt();
			if( R==-1 && N==-1 ) break;
			int[] x = new int[N+1];
			x[N] = Integer.MAX_VALUE; //solve2でx[N]を番兵として使用する
			for(int i=0; i<N; i++) x[i] = scanner.nextInt();
			
			System.out.println( solve(N,R,x) );
		}
	}
	
	int upper_bound(int[] array, int li, int ri, int k){
		int lb = li - 1, ub = ri;
		//解の存在範囲が１より大きい間、反復
		while(ub - lb > 1){
			int mid =(lb + ub) / 2;
			if( array[mid] <= k )	//midが条件を満たせば、解の存在範囲は[mid,ub)
				lb = mid;
			else				//midが条件を満たさなければ、解の存在範囲は[lb,mid)
				ub = mid;
		}
		return ub;
	}
	//greedy 2分探索(upper_bound)　ソートしているのでO(n log n)
	int solve(int N, int R, int[] x){
		Arrays.sort(x);
		int res = 0;
		for(int i = 0; i < N; ++res){
			i = upper_bound(x, 0, N, x[i]+R);
			i = upper_bound(x, i-1, N, x[i-1]+R);
		}
		return res;
	}
	//greedy 線形探索　 ソートするのでO(n log n)
	int solve2(int N, int R, int[] x){
		int ans = 0;
		int i = 0;
		Arrays.sort(x);
		while( i < N ){
			int s = x[i++]; //左端
			while( x[i] <= s+R ) i++;
			int p = x[i-1]; //中央
			while( x[i] <= p+R ) i++;
			//x[i-1]が右端
			ans++;
		}
		return ans;
	}
}