UVa 10327 題解 — C++

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

Flip Sort (ZeroJudge a539.)

題目

排序在電腦科學中是一個重要的部分。已經有許多優秀的排序演算法被提出。在這個問題中我們將討論一種排序的方式，就是你只能交換相鄰的 2 個元素。如果你想一下的話，你會瞭解以這樣的方式總是可以將一些數字排序。(註：我們通常稱這種排序方式為 Bubble Sort)

給你一串整數，請你用上述的方法來將之由小到大排序。要請你求出最少要交換幾次。例如給你 "1 2 3"，那需要交換的次數為 0，因為已經排好了。如果給你 "2 3 1"，則最少需要交換2次才可排好序。("2 3 1" → "2 1 3" → "1 2 3")

輸入 / 輸出說明

輸入說明	輸出說明
輸入將以正整數 𝑁（𝑁 ≤ 1000）開始。接下來的幾行將有 𝑁 個整數。輸入將以 EOF 終止。	對於每個資料集列印 "Minimum exchange operations : 𝑀"，其中 𝑀 是執行排序所需的最小翻轉操作。每一種情況都用一行來表示

解題思路

將 m 作為計算次數的變數，先歸零再做 bubble sort，然後每次交換的時候將次數加 1 即可求得正確解答。

bubble sort (氣泡排序法)
就是將鄰近的兩的數字交換，將大的往右傳遞（類似氣泡不斷浮出水面），最終傳遞到的數字就是未排序中最大的。
假設我們要排序 7 5 1 2 3，第一次排序（最大的會浮到最右邊）順序如下，後面依此類推，不再演示：

範例程式碼

#include <iostream>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, j, n, m, temp;
	
	while (cin >> n) {
		int a[n];
		m = 0;
		
		for (i=0;i<n;i++)
			cin >> a[i];
			
		for (i=0;i<n-1;i++) {
			for (j=0;j<n-i-1;j++) {
				if (a[j] > a[j+1]) {
					temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
					
					m++;
				}
			}
		}
		
		cout << "Minimum exchange operations : " << m << endl;
	}

	return 0;
}

運行結果

AC (5ms, 336KB)

tags: CPE 2星

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