題目描述
拉里有一串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)開始，由陣列的最尾端開始往前旋轉，把最小的數值旋轉至第二個元素的位置，如此一來就可以完成這三旋轉的氣泡排序法。
至於該如何判斷這三旋轉的氣泡排序法是否排序成功，只需要在排到最後時，判斷最後兩個元素的順序是否正確即可，因為在這最後兩個元素之前的元素都已經確定排序好了。
參考答案
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | 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"); } } } |
