e561. 00299 - Train Swapping
Tags :
Accepted rate : 1300人/1342人 ( 97% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-10-29 11:59

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
3
3
1 3 2
4
4 3 2 1
2
2 1
Sample Output #1
Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
Hint :
Tags:
出處:
UVA [管理者: ig99lp33lp33 (위즈원) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
29711 yilson0983@g ... (Cookie) e561
Train Swapping
1839 2022-03-23 18:52
39309 toseanlin@gm ... (Dr. SeanXD) e561
解題思路
423 2024-02-05 01:24