题意分析

题目要求我们计算将一个无序序列通过相邻元素的交换操作变成有序序列所需的最少交换次数。每次只能交换相邻的两个元素。例如，序列 2 8 0 3 可以通过3次相邻交换变成有序序列 0 2 3 8。

解题思路

1. 逆序对的概念：在序列中，如果一个元素比它后面的某个元素大，那么这两个元素构成一个逆序对。例如，在序列 2 8 0 3 中，(2,0)、(8,0)、(8,3) 都是逆序对。
2. 逆序对与最少交换次数的关系：最少交换次数等于序列中的逆序对数量。因为每次相邻交换可以消除一个逆序对。
3. 计算逆序对数量的方法：
   • 暴力法：对于每个元素，遍历其后面的所有元素，统计比它小的元素的数量。时间复杂度为 O(N^2)，适用于 N 较小的情况（如 N ≤ 1000）。
   • 归并排序法：在归并排序的过程中统计逆序对的数量，时间复杂度为 O(N log N)，适用于较大的 N。

标程代码

方法一：暴力法（O(N^2)）

#include <iostream>
#include <vector>
using namespace std;

int countInversions(const vector<int>& arr) {
    int inv_count = 0;
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] > arr[j]) {
                inv_count++;
            }
        }
    }
    return inv_count;
}

int main() {
    int scenarios;
    cin >> scenarios;
    for (int s = 1; s <= scenarios; s++) {
        int n;
        cin >> n;
        vector<int> arr(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        int inversions = countInversions(arr);
        cout << "Scenario #" << s << ":" << endl;
        cout << inversions << endl << endl;
    }
    return 0;
}

方法二：归并排序法（O(N log N)）

#include <iostream>
#include <vector>
using namespace std;

int merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    int inv_count = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            inv_count += (mid - i + 1);
        }
    }

    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    while (j <= right) {
        temp[k++] = arr[j++];
    }

    for (i = left, k = 0; i <= right; i++, k++) {
        arr[i] = temp[k];
    }

    return inv_count;
}

int mergeSort(vector<int>& arr, int left, int right) {
    int inv_count = 0;
    if (left < right) {
        int mid = left + (right - left) / 2;
        inv_count += mergeSort(arr, left, mid);
        inv_count += mergeSort(arr, mid + 1, right);
        inv_count += merge(arr, left, mid, right);
    }
    return inv_count;
}

int countInversions(vector<int>& arr) {
    return mergeSort(arr, 0, arr.size() - 1);
}

int main() {
    int scenarios;
    cin >> scenarios;
    for (int s = 1; s <= scenarios; s++) {
        int n;
        cin >> n;
        vector<int> arr(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        int inversions = countInversions(arr);
        cout << "Scenario #" << s << ":" << endl;
        cout << inversions << endl << endl;
    }
    return 0;
}

代码解释

1. 暴力法：

   • countInversions 函数通过双重循环统计逆序对数量。
   • 主函数读取输入，调用 countInversions 并输出结果。

2. 归并排序法：

   • merge 函数在合并两个有序子数组时统计逆序对数量。
   • mergeSort 函数递归地将数组分成两半，分别排序并统计逆序对。
   • countInversions 函数初始化归并排序过程。
   • 主函数读取输入，调用 countInversions 并输出结果。

两种方法都能正确计算最少交换次数，但归并排序法效率更高，适合处理较大的数据集。暴力法简单直接，适用于小规模数据。