北大ACM试题1012-约瑟夫环

简直就是悲伤中的战斗机。。。居然又是两个月没更新了。。原因是搬新家而且老婆孩子来了，具体啥原因真心是一言难尽。。。但是真的感觉有了家庭就很难提起劲来学习了。。。每天也没干啥就过去了。。。这样不行。。。说好的还贷7000呢，还想不想过了！！！

废话到此结束，1012就是经典的约瑟夫环的变种，刚开始拿到的时候想着这还不简单么，规则都订好了，剩下就是重复重复再重复么，这还不简单，电脑最擅长了，稍微想了想就写了如下代码：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main_1012_Joseph {

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		List<String> output = new ArrayList<String>();
		String kk = "";
		while(!(kk = cin.nextLine()).equals("0")){
			int k = Integer.parseInt(kk);
			int m = k+1;
			int index = -1;
			//标记是否被杀掉
			int[] isKilled = new int[k*2];
			for(int i=0;i<k*2;i++){
				isKilled[i] = -1;
			}
				
			for(int i=0;i<k;i++){
				//重要优化，考虑最后一次杀得是坏人，必然是杀第k+1个人或者第2k个人
				while(m%(k+1) != 0 && m%(k+1) != 1){
					m++;
				}
				//考虑m很大的时候，只有余数是有效的
				int temp = m % (k*2 - i);
				temp = (temp==0?m:temp);
				int j = 1;
				while(j <= temp){
					index ++ ;
					if(index >= (k*2)){
						index = index - (k*2);
					}
					//依次移动，没有被杀就+1
					if(isKilled[index] == -1){
						j++;
					}
				}
				//index小于k说明杀得是好人
				if(index < k){
					i = -1;
					index = -1;
					for(int l=0;l<k*2;l++){
						isKilled[l] = -1;
					}
					m++;
				}else{
					isKilled[index] = i;
				}
			}
			output.add(m+"");
		}
		cin.close();
		for(int i=0;i<output.size();i++){
			System.out.println(output.get(i));
		}
	}
}

结果必须是不出意外的TLE了。。。自己测试的时候输入10都半天没反应。。。想了想，最费时间的应该是每次m++的时候 都要初始化一个数组，太耗时了，后来的m越来越大，就没反应了。。。没招了，去网上看了看思路，原来约瑟夫环都有固定的公式了。。。剩下的就简单多了。。。

import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		//用于记录已有的值，要不还是TLE
		int[] origin = new int[15];
		String kk = "";
		while(!(kk = cin.nextLine()).equals("0")){
			int k = Integer.parseInt(kk);
			if(origin[k] != 0){
				System.out.println(origin[k]);
				continue;
			}
			int m = k+1;
			int joseph[] = new int[30];
				
			for(int i=1;i<=k;i++){
				//重要优化，考虑最后一次杀得是坏人，必然是杀第k+1个人或者第2k个人
				while(m%(k+1) != 0 && m%(k+1) != 1){
					m++;
				}
				//莫名的忧伤，一个固定的推导公式，具体怎么推出来的不了解。。。数学没有学好。。
				joseph[i] = (joseph[i-1]+m-1) % (k*2-i+1);
				if(joseph[i] < k){
					i = 0;
					m++;
				}
			}
			if(origin[k] == 0){
				origin[k] = m;
			}
			System.out.println(m);
		}
		cin.close();
	}
}

由此可见一个好算法的重要性了，要不然算到天黑还是出不来的。。。。最近开始着手准备跳槽了，没事看看书，编编程，让自己每天都感觉到进步吧，加油~