iT邦幫忙

2023 iThome 鐵人賽

DAY 29
0
SideProject30

UVA題型研究系列 第 29

DAY29:Train Swapping

  • 分享至 

  • xImage
  •  

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

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

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

範例輸入 #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.
題解:輸入火車的排列狀態,輸出需要交換多少次以排好順序

# 定義一個函數 `solve`,接受兩個參數:n(火車數量)和 nums(火車陣列)
def solve(n, nums):
    count = 0  # 初始化交換次數為 0
    # 使用兩個巢狀迴圈來遍歷所有可能的火車對
    for i in range(n-1): # 外層迴圈的目的是確保所有的元素都被處理到。
        for j in range(n-i-1): # 內層迴圈的目的是進行相鄰元素的比較和交換
            # 如果前一節火車的序號大於後一節火車的序號,則進行交換
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
                count += 1  # 交換次數加一
    # 回傳交換次數的訊息,使用字串格式化語法
    return f'Optimal train swapping takes {count} swaps.'

# 讀取輸入中的測試案例數量
T = int(input())
# 迴圈遍歷每個測試案例
for t in range(T):
    n = int(input())  # 讀取火車數量
    nums = list(map(int, input().split()))  # 讀取火車序號列表
    # 呼叫 solve 函數並印出結果
    print(solve(n, nums))

上一篇
DAY28:Tell me the frequencies!
下一篇
DAY30:cola
系列文
UVA題型研究30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言