水平1021回転キュー解題(JAVA)

質問リンク

質問する

志敏にはN個の要素を含む双方向ループQがある.志敏はこのキューからいくつかの要素を抽出したいと思っています.
志敏はこのキューで次の3つの演算を実行できます.
最初の要素を抽出します.この操作を実行すると、元のキューの要素はa 1、...、akだったのはa 2だったのか...、akと同じです.
1グリッドを左に移動します.この操作を実行すると、a 1,...、akはa 2、...、ak,a 1になります.
1つ右に移動します.この操作を実行すると、a 1,...、akはak,a 1,...,ak-1になります.
キューに最初に含まれる数Nが与えられる.そしてジミンが抽出する要素の位置を与える(この場所は最初のキューの場所です.)このとき、所定の順序でその要素を抽出するために必要な2、3回の演算の最大値を出力するプログラムを作成してください.

入力

最初の行は、キューサイズNと抽出する数Mを与える.Nは50以下の自然数、MはN以下の自然数である.2列目は志敏が引く数字を順番に与える位置です.位置は1以上、N以下の自然数である.

しゅつりょく

最初の行に問題の答えを出力します.

に答える

まず、キューにすべての値を入れ、必要な数値が表示されるまでキューを回転します.
次に回転数を計算し、回転数がキューの大きさの半分より大きい場合は反対のホイールで大きく回転する.すなわち、回転方向が現在の銭方向と逆であれば、回転数が最小となる.
キューに1.2.3.4.5があるとします.最初の要素を5の上に置きたい場合は、左に1回、または右に4回回転します.ここから左回転数+右回転数=要素の個数がわかります.つまり、要素の個数-現在の回転数=反転数です.

ソースコード

import java.util.*;
import java.io.*;
public class Main{
    
    public static void main(String [] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int numberOfNumber = Integer.parseInt(st.nextToken());
        final int NUMBER_OF_POP = Integer.parseInt(st.nextToken());
        
        Queue<Integer> queue = new LinkedList<Integer>();
        for(int i=1;i<=numberOfNumber;i++) {
            queue.add(i);
        }
        int answer = 0;
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<NUMBER_OF_POP;i++) {
            int moving = 0;
            int want = Integer.parseInt(st.nextToken());
            while(queue.peek() != want) {
                int temp = queue.poll();
                queue.add(temp);
                moving++;
            }
            if(moving > numberOfNumber/2) {
                moving = numberOfNumber - moving;
            }
            answer += moving;
            numberOfNumber--;
            queue.poll();
        }
        
        sb.append(answer);
        sb.append("\n"); 
        
        bw.write(sb.toString());
        
        bw.flush();
        br.close();
        bw.close();
        
    }

    
}