#45214: python思路


chenwei980503@gmail.com (陳維(Z))

學校 : 新北市立北大高級中學
編號 : 278351
來源 : [101.12.86.8]
最後登入時間 :
2025-04-05 14:32:44
e561. 00299 - Train Swapping -- UVA | From: [101.10.11.98] | 發表日期 : 2025-01-26 17:22

解題思路

解題的核心在於計算一個列表的逆序對數量。使用雙重迴圈比較每一對元素,當 b[i] > b[j]i < j)時,表示存在一個逆序對,計數器增加。

  • 計算過程
    1. 初始化交換計數器 s 為 0。
    2. 使用兩層迴圈遍歷列表的所有可能的元素對。
    3. 每次找到一對逆序對時,將計數器 s 增加 1。

這種方法的時間複雜度為 O(l2)O(l2),在 l 较大时效率较低,但对於小逸數列的情況仍然可以接受。

  • 特例處理
    • 當 l 為 0 時,直接輸出 "Optimal train swapping takes 0 swaps."
     for i in range(len(b)):
for j in range(i+1, len(b)):
if b[i]>b[j]:
s+=1
 
ZeroJudge Forum