DAY 19
0

Day 0x13 UVa299 Train Swapping

題意

• 輸入火車的排列狀態，輸出需要交換多少次以排好順序
• 需要注意的有：
1. 輸入第一行一個整數 `N` 代表測資數
2. 每筆測資第一行 `L` 代表火車長度 (0 ≤ L ≤ 50)
3. 每次交換只能對調相鄰兩車廂
4. 輸出格式
• `Optimal train swapping takes S swaps.`

解法

• 輸入測資數 `N` 並用 `while` 迴圈重複，再讀每筆測資長度 `L` 並存入整數陣列中
``````int N;
int L;
int train[50] = {0};

scanf("%d", &N);        //number of case

while(N--){

scanf("%d", &L);    //length of train

for(i = 0; i < L; i++){
scanf("%d", &train[i]);
}
...
}
``````
• 因為 `L` 的範圍很小，所以用泡沫排序的概念計算交換次數即可 (一星題嘛 XD)
``````int count = 0;

for(i = 0; i < L - 1; i++){
for(j = 0; j < L - 1 - i; j++){
if(train[j] > train[j + 1]){
temp = train[j];
train[j] = train[j + 1];
train[j + 1] = temp;
count++;
}
}
}

printf("Optimal train swapping takes %d swaps.\n", count);
``````
• C code
``````#include<stdio.h>

int main(){

int N;
int L;
int train[50] = {0};
int i, j;
int temp;

scanf("%d", &N);        //number of case

while(N--){

scanf("%d", &L);    //length of train

int count = 0;

for(i = 0; i < L; i++){
scanf("%d", &train[i]);
}

for(i = 0; i < L - 1; i++){
for(j = 0; j < L - 1 - i; j++){
if(train[j] > train[j + 1]){
temp = train[j];
train[j] = train[j + 1];
train[j + 1] = temp;
count++;
}
}
}

printf("Optimal train swapping takes %d swaps.\n", count);

}

return 0;
}
``````