recamanssequence.java

PKU中一些数据结构基本算法题的java实现

package PKU.DP;
import java.util.*;


public class RecamansSequence {

	static boolean[] flag = new boolean[3012501];
	static int[] result = new int[500001];
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		Arrays.fill(result, -1);
		result[0] = 0;
		for(int i=1;i<=500000;i++){
			int last = result[i-1];
		    if(last-i>0 && !flag[last-i])
		    {

		        result[i] = last-i;

		        flag[last-i] = true;

		    }

		    else

		    {

		        result[i] = last+i;

		        flag[last+i] = true;

		    }
		}
		while(cin.hasNext()){
			int x = cin.nextInt();
			if(x==-1) break;
			
			System.out.println(result[x]);
		}
		

	}
	


}