b373: [福州19中]車廂重組

2019-08-14

內容

車廂重組 carry

【問題描述】

在一個舊式的火車站旁邊有一座橋，其橋面可以繞河中心的橋墩水平旋轉。一個車站的職工發現橋的長度最多能容納兩節車廂，如果將橋旋轉 180 度，則可以把相鄰兩節車廂的位置交換，用這種方法可以重新排列車廂的順序。於是他就負責用這座橋將進站的車廂按車廂號從小到大排列。他退休後，火車站決定將這一工作自動化，其中一項重要的工作是編一個程序，輸入初始的車廂順序，計算最少用多少步就能將車廂排序。

車廂編號從 1 開始。

輸入

輸入文件有兩行數據，第一行是車廂總數 N（不大於 10000），第二行是 N 個不同的數表示初始的車廂順序，每 2 個數之間用一個空格隔開。

4
4 3 2 1

輸出

一個數據，是最少的旋轉次數。

6

解題思路

因為橋一次只能換兩節車廂，所以其實就是在問 bubble sort(氣泡排序) 的交換次數，實作氣泡排序並在交換時紀錄次數即可。

這題也可以用 merge sort(合併排序) 來做，時間複雜度可以從 O(n²) 降到 O(nlogn)，但由於測資過弱所以沒有具體意義。

完整程式碼

AC (3ms, 124KB)

#include <stdio.h>
#define SWAP(x, y) x^=(y^=(x^=y))

int index[10000];

int main()
{
    int n, max, count;
    while (scanf(" %d", &n) == 1)
    {
        max = n - 1, count = 0;
        for (int i = 0; i < n; i++)
            scanf(" %d", &index[i]);
        for (int i = 0; i < max; i++)
        {
            for (int j = 0; j < max - i; j++)
            {
                if (index[j] > index[j + 1])
                    SWAP(index[j], index[j + 1]), count++;
            }
        }
        printf("%d\n", count);
    }
    return 0;
}