白駿-1158号(ジョセフ問題)

質問元:https://www.acmicpc.net/problem/1158
質問する

ジョセフス問題は以下の通りです.

1番からN番までは、N人が1つの円に座り、正の整数K(≦N)を与えます.今は順番にK人目を除いています.一人が取り除かれると、残りの人からなる円に沿ってこの過程が続きます.この過程はN人全員がクリアされるまで続く.円上の人々が消去される順序を(N,K)−ジョセフス配列と呼ぶ.例えば、(7,3)−ジョセフス配列<3,6,2,7,5,1,4>である.

NとKをあげると(N,K)-ジョセフスシーケンスを求めるプログラムを書きます.

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        StringBuilder sb = new StringBuilder("<");
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int K = scanner.nextInt();

        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 1; i <= N; i++) {
            queue.offer(i);
        }

        while (!queue.isEmpty()) {
            for (int i = 0; i < K - 1; i++) {
                queue.offer(queue.poll());
            }
            sb.append(queue.poll()).append(", ");
        }
        sb.setLength(sb.length() - 2);
        System.out.println(sb.append(">"));

        scanner.close();
    }

}

プロトタイプQ概念を用いて問題を解く.

削除される人が見つかる前に、前の投票()の人をキュー()に再送信し、キューに保持します.