題目描述

拉里有一串N個數字的陣列A,A={a1,a2,…,aN-1,aN},每個數字ai都是獨特不重複的。拉里想要用他的機器人來排序這個陣列A,他的機器人可以不限次數地任意旋轉某3個連續相同的元素,舉例來說:ABC旋轉一次之後會變成BCA,再旋轉一次會變成CAB,再旋轉一次又會回到ABC。



如果A={1,6,5,2,4,3},然後機器人旋轉了(6,5,2),A的內容就會變成{1,5,2,6,4,3}。

計算每組測試資料,並在新的一行輸出拉里的機器人是否可以成功排序陣列A。如果可以,輸出「YES」;如果不行,輸出「NO」。

原題網址

輸入格式

輸入第一行包含一個整數T,為測試資料的數量,範圍在1到10之間(包含1和10)。
接下來的的2T行,每兩行表示一組測試資料。一組測試資料的第一行是一個整數N,為A陣列的大小,範圍在3到1000之間(包含3和1000)。第二行輸入N個整數表示A陣列的內容,可以用ai來表示輸入的元素數值,數值範圍在1到N之間(包含1和N),每個元素的數值都不相同。

輸出格式

計算每組測試資料,並在新的一行輸出拉里的機器人是否可以成功排序陣列A。如果可以,輸出「YES」,否則輸出「NO」。

範例輸入

3
3
3 1 2
4
1 3 4 2
5
1 2 3 5 4

範例輸出

YES
YES
NO

額外解釋

用Aj表示每次旋轉後A陣列的內容。

測試資料1:

A0={3,1,2}→rotate(3,1,2)→A1={1,2,3}

A陣列已經排序好了,因此輸出「YES」。

測試資料2:
A0={1,3,4,2}→rotate(3,4,2)→A1={1,4,2,3}
A1={1,4,2,3}→rotate(4,2,3)→A2={1,2,3,4}
A陣列已經排序好了,因此輸出「YES」。

測試資料3:
沒有辦法將A陣列排序好,輸出「NO」。

解題概念

可以把這題所用到的演算法,當作是氣泡排序法(Bubble Sort)的改版。原始的氣泡排序法一次旋轉兩個元素,而這裡用到的演算法一次需旋轉三個元素。我們可以從第一個元素(陣列索引0)開始,由陣列的最尾端開始往前旋轉,把最小的數值旋轉至第一個元素的位置。接著再從第二個元素(陣列索引1)開始,由陣列的最尾端開始往前旋轉,把最小的數值旋轉至第二個元素的位置,如此一來就可以完成這三旋轉的氣泡排序法。

至於該如何判斷這三旋轉的氣泡排序法是否排序成功,只需要在排到最後時,判斷最後兩個元素的順序是否正確即可,因為在這最後兩個元素之前的元素都已經確定排序好了。

參考答案

import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);
        int testCase = sc.nextInt();
        TestCase:
        while (testCase-- > 0) {
            final int n = sc.nextInt();
            final int[] a = new int[n];
            for (int i = 0; i < n; ++i) {
                a[i] = sc.nextInt();
            }
            final int n_dec3 = n - 3;
            for (int i = 0; i <= n_dec3; ++i) {
                for (int j = n_dec3; j >= i; --j) {
                    final int x = a[j];
                    final int y = a[j + 1];
                    final int z = a[j + 2];
                    if (z <= y && z <= x) {
                        a[j] = z;
                        a[j + 1] = x;
                        a[j + 2] = y;
                    } else if (y <= x && y <= z) {
                        a[j] = y;
                        a[j + 1] = z;
                        a[j + 2] = x;
                    } else{
                        // don't need to rotate
                    }
                }
            }
            System.out.println(a[n - 2] <= a[n - 1] ? "YES" : "NO");
        }
    }
}