題目描述

約翰‧華生替整數陣列做出了一種運算方式，稱為「右循環旋轉」。這種運算方式，可以將陣列最右邊的元素移出，並插入到陣列的最左邊。他為了要考驗夏洛克的能力，會給夏洛克一個整數陣列，接著再告訴夏洛克進行「右循環旋轉」的次數之後，再給幾個陣列的索引值，問夏洛克此時陣列的每個索引值所對應的元素值是多少。



原題網址

已不存在。

輸入格式

輸入第一行輸入三個整數N、K、Q，以空格隔開。N表示整數陣列的長度，範圍在1到105之間(包含1和105)。K表示要對陣列進行「右循環旋轉」的次數，範圍在1到105之間(包含1和105)。Q表示要回答元素值的索引值的數量，範圍在1到500之間(包含1和500)。

輸入的第二行為N個用空格分隔的整數，範圍在1到105之間(包含1和105)。

接下來的Q行，每行都是要回答的元素值的索引值，範圍在0到N-1之間(包含0和N-1)。

輸出格式

針對每行要回答元素值的索引值進行輸出，每回答一個索引值就將其對應的元素值輸出到獨立的一行。

範例輸入

3 2 3
1 2 3
0
1
2

範例輸出

2
3
1

額外解釋

陣列為：[1 2 3]。

要進行「右循環旋轉」2次。

旋轉後的陣列為：[2 3 1]。

索引0的元素為「2」，輸出「2」；索引1的元素為「3」，輸出「3」；索引2的元素為「1」，輸出「1」。

解題概念

由於進行「右循環旋轉」的次數可能會高達105，我們在一開始就必須計算K除以N，再取餘數，作為新的K值，避免旋轉好幾圈會做太多無效的重複搬移，而導致程式執行時間太長。然而，即便如此，如果剛好遇到要「右循環旋轉」N-1次的話，由於陣列長度也會高達105，因此可能也需要耗費很長的執行時間。

其實仔細想想的話，就會發現根本就不需要真的去搬移陣列中的元素來取得最後索引值所對應的元素值。假設「右循環旋轉」的次數為2次，然後華生問的索引值為2的話，只要直接給它索引值為0的元素不就好了嗎？所以如果「右循環旋轉」的次數為2次，然後華生問的索引值為1的話，就要給他索引值為N-1的元素。我們可以推導出新索引值的公式如下：

新索引值 = (舊索引值 - K + N) % N

參考答案

import java.util.*;

public class Solution {

    public static void main(final String[] args) {
        final Scanner in = new Scanner(System.in);
        final int N = in.nextInt();
        int K = in.nextInt();
        final int Q = in.nextInt();

        final int[] A = new int[N];

        for (int i = 0; i < N; ++i) {
            A[i] = in.nextInt();
        }
        K %= N;
        for (int i = 0; i < Q; ++i) {
            final int X = in.nextInt();
            System.out.println(A[(X - K + N) % N]);
        }
    }
}