UVa 00299 – Train Swapping
In the old railway stations, you may encounter a few of the remaining "carriage switchers." These "carriage switchers" are employees of the railway department whose main job is to rearrange the carriages of trains. Once the carriages are arranged in the optimal order, all the train drivers need to do is unload them one by one. The term "carriage switcher" originated from the first person who executed this task at a station near a railway bridge. This bridge does not open vertically but rotates around a central pillar in the middle of the river. By rotating the bridge 90 degrees, ships can pass through either to the left or right. The first "carriage switcher" discovered that this bridge can accommodate up to two carriages at a time. By rotating the bridge 180 degrees, the carriages can switch positions. (The drawback is that the carriages face opposite directions, but since the train carriages can move in any direction, it doesn't matter.) Nowadays, almost all "carriage switchers" have been phased out, and the railway company hopes to automate their operations. Your task is to write a program that calculates the minimum number of times two adjacent carriages need to be exchanged to arrange all the carriages in order.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line of input contains an integer N, which represents the number of test cases. Each test case begins with an integer L (0 ≤ L ≤ 50) on the first line, representing the length of the train. The second line contains a permutation of numbers from 1 to L, indicating the current order of the train carriages. The goal is to arrange the train carriages in the order from 1 to L. | For each test case, please output: "Optimal train swapping takes S swaps.", where S represents the minimum number of swaps required. Grammatical rules allow for the omission of the "s" for singular numbers. |
| 3 3 1 3 2 4 4 3 2 1 2 2 1 | Optimal train swapping takes 1 swaps. Optimal train swapping takes 6 swaps. Optimal train swapping takes 1 swaps. |
Thought Process
You can use Bubble Sort to solve this problem. Each time you perform a swap, increment a variable to keep track of the number of swaps. Finally, output the total number of swaps made.
Sample Code－ZeroJudge E561: Train Swapping
#include <iostream>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for (int i = 0; i<N; i++)
{
int len;
cin >> len;
vector<int>num;
for (int j = 0; j<len; j++)
{
int tmp;
cin >> tmp;
num.push_back(tmp);
}
int ans = 0;
for (int j = 0; j<len; j++)
{
for (int k = 0; k<len-1; k++)
{
if (num[k] > num[k+1])
{
swap(num[k], num[k+1]);
ans++;
}
}
}
cout << "Optimal train swapping takes " << ans << " swaps.\n";
}
}
//ZeroJudge E561
//Dr. SeanXD