[Java]白俊2164号

1479 ワード
baekjoon algorithm テキストリンク

我是白俊2164号。


カード。


質問する


カードがN枚あります.各カードには順番に1からNの番号が貼られており、1番札が一番上に、N番札が一番下に、順番にカードが置かれています.
カードが1枚残るまで、以下の動作を繰り返します.まず、一番上の札を地面に投げます.そして、一番上のカードを一番下のカードの下に移動します.
例えば、N=4とする.カードは一番上から1234の順番に並べられています.1を投げてまだ234残っています.ここで2を一番下に移動すると342です.3を42に、4を下に移動すると24になります.最後に2を捨てて、残りのカードは4になりました.
Nが付与されると、最後に残ったカードを取得するプログラムを作成してください.

入力


第1行は整数N(1≦N≦500000)を与える.

しゅつりょく


最初の行に残っているカード番号を出力します.

例



コード#コード#

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		Queue<Integer> queue = new LinkedList<>();
		
		int N = Integer.parseInt(br.readLine());	
		
		for(int i=1; i<=N; i++)
			queue.offer(i);
		
		while(queue.size()>1) {
			queue.poll();
			queue.offer(queue.poll());
		}
		
		System.out.println(queue.poll());
	}
}

に答える

Queueを用いて問題を解決した.
1からNまでoffer()を用いてキューを挿入する.
queueの整数値がpoll()である後、queueの整数値()をポーリングし、最後にoffer()である.キューに1つの要素しか残っていないwhile文に繰り返し、残りの要素を出力します.
switchとifの性能比較
[アルゴリズム/標準]1699:平方和(python)