時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
老車站的調車員利用旋轉橋交換相鄰的兩節車廂，以重新排列列車。現在鐵路公司希望將這項工作自動化。
給定車廂目前的排列，請求出只交換相鄰兩節車廂時，將車廂依編號由小到大排好所需的最少交換次數。
輸入格式
第一行是測試資料筆數 N。每筆資料先有一行整數 L，表示車廂數，0 ≤ L ≤ 50；接著一行是 1 到 L 的一個排列，表示目前車廂順序。
輸出格式
每筆資料輸出 Optimal train swapping takes S swaps.，其中 S 是最少交換次數。
題目來源：UVa 299 — Train Swapping。 原題：https://onlinejudge.org/external/2/299.pdf
範例測資
範例輸入 1
3 3 1 3 2 4 4 3 2 1 2 2 1
範例輸出 1
Optimal train swapping takes 1 swaps. Optimal train swapping takes 6 swaps. Optimal train swapping takes 1 swaps.
請先登入後再提交程式碼
討論與題解
載入討論區…