UVa 299 題解 — C++

此筆記為UVa 299的題目詳解，包含解題思路、C++範例程式碼。

Train Swapping (ZeroJudge e561.)

題目

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

輸入 / 輸出說明

輸入說明	輸出說明

解題思路

這題利用氣泡排序法（Buble Sort）即可解決。

範例程式碼

#include <iostream>
using namespace std;

int main ()
{
	int i, j;
	int n, l;
	
	cin >> n;
	
	while (n > 0) {
		cin >> l;
		
		int train[l], t = 0;
		
		for (i=0;i<l;i++)
			cin >> train[i];
			
		for (i=0;i<l;i++) {
			for (j=0;j<l-i-1;j++) {
				if (train[j] > train[j+1]) {
					swap(train[j], train[j+1]);
					t++;
				}
			}
		}
		
		cout << "Optimal train swapping takes " << t << " swaps." << endl;
		
		n--;
	} 

	return 0;
}

運行結果

AC (2ms, 316KB)

tags: CPE 1星

查看更多資訊請至：https://www.tseng-school.com/