10327 Flip Sort

題目連結

題目敘述

在計算機科學中，排序是非常重要的一環
幾乎所有問題只要對資料進行排序後，都能更有效率地解決
雖然已經有許多演算法可以達到 n log_n 的下界
本題探討的是一種只允許「翻轉」（Flip）操作的新方法──每次只能交換兩個相鄰的元素
細想之下，你會發現，只要使用翻轉，就能將任意一組數字排序
給定一組整數，使用「翻轉」操作將它們由小到大排序
並計算所需的最少翻轉次數

翻轉操作：交換序列中兩個相鄰的元素

輸入格式

• 第一行：正整數 N（N ≤ 1000），代表接下來會有 N 個待排序整數
• 第二行：N 個整數，以空白分隔
• 之後若還有另一組資料，則重複以上兩行，直到檔案結尾

輸出格式

對於每一組資料，輸出一行：

Minimum exchange operations : M  

• 其中 (M) 為完成排序所需的最少翻轉次數。

解題思路

實作一個 Bubble Sort
並在進行交換時使用一個變數紀錄交換次數

程式碼

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(n); // 初始化儲存整數的陣列
        int cnt = 0;
        for (auto &i : v) cin >> i; // 進行待排列整數的輸入
        for (int i = 0; i < n-1; i++) for (int j = 0; j < n-1-i; j++) if (v[j] > v[j+1]) swap(v[j], v[j+1]), cnt++; // 使用巢狀實作泡沫排序法
        cout << "Minimum exchange operations : " << cnt << '\n'; // 按照題目要求格式輸出
    }
}