- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- public class Main {
- // 打表数据...不打表我这个程序会超时...虽然我机子是秒出的
- int a[] = new int[] { 2, 7, 5, 30, 169, 441, 1872, 7632, 1740, 93313,
- 459901, 1358657, 2504881, 13482720 };
- public static void main(String[] args) throws NumberFormatException,
- IOException {
- BufferedReader read = new BufferedReader(new InputStreamReader(
- System.in));
- int k;
- int m = 0;
- int num = 0;
- int killed = 0;
- while ((k = Integer.parseInt(read.readLine())) != 0) {
- loop: for (m = k + 1;;) {
- num = 0;
- if (m % (k + 1) == 0 || (m - 1) % (k + 1) == 0) {
- if (m % (2 * k) == 0) {
- num = 2 * k - 1;
- } else {
- num = m % (2 * k) - 1;
- }
- int len = 2 * k;
- for (killed = 0; killed < k; killed++) {
- if (num < k) {
- m++;
- continue loop;
- }
- len--;
- num--;
- num = (num + 1 + m) % len - 1;
- if (num == -1) {
- num = len - 1;
- }
- }
- break;
- } else {
- m += k - 1;
- }
- }
- System.out.println(m);
- }
- }
- }
题目：http://acm.pku.edu.cn/JudgeOnline/problem?id=1012
思路：约瑟夫环，讨论里面推荐打表在提交，我试了一下我的程序，遗憾的是，还是超时了，只能打表搞。。。虽然在我机子上跑不能说秒出，但还是挺快的。时间复杂度已经O(n^2)了，哎。。。