高中生程式解題系統 e561: 00299 - Train Swapping－資工趴趴熊的小天地

Content

在老舊的火車站，您也許會遇到少數僅存的"車箱置換員"。
"車箱置換員"是鐵路部門的員工，主要工作就是重新排列火車車廂。
一旦以最佳順序排列了車廂，所有火車司機要做的就是將車廂逐一卸下即可。
"車箱置換員"源自在鐵路橋附近的車站中執行此任務的第一人。
這座橋並不會垂直打開，而是繞著河中央的一根支柱旋轉。將橋旋轉90度後，船隻就能向左或向右駛過。
第一位"車箱置換員"發現，這座橋最多可以在其上運行兩個車廂，通過將橋旋轉180度，車廂就能切換位置。
(缺點是車廂面向相反的方向，但是火車車廂可以以任何一種方式移動，所以沒差）。
現在幾乎所有的"車箱置換員"都已經淘汰了，鐵路公司希望將其操作自動化。
你的任務就是寫一個程式，該程式要計算最少需要交換幾次兩個相鄰車廂，才能將所有車廂依序排好。

Input

輸入的第一行包含一個整數N，N代表測資數量。
每組測資的第一行包含一個整數L (0 ≤ L ≤ 50)，L代表火車的長度。
第二行包含數字1到L的排列，表示火車車廂的當前順序。
需要將火車車廂依照編號1到L的順序排好。

Output

對於每組測資，請輸出：
"Optimal train swapping takes S swaps."，S代表最少交換次數。

Sample Input #1

Sample Output #1

Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.

泡泡排序法

def bubbleSort(arr):
    n = len(arr)
    ans=0
    # 遍历所有数组元素
    for i in range(n):
 
        # Last i elements are already in place
        for j in range(0, n-i-1):
 
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]
                ans+=1
    return arr,ans
t=int(input())
for _ in range(t):
  no=int(input())
  arr=list(map(int,input().split()))
  a,b=bubbleSort(arr)
  print(f'Optimal train swapping takes {b} swaps.')