题目内容： 山迪要出席一个周末表演晚会，他在会上要表演卡片魔术。他有n（0＜n≤100）张卡片，每张卡片上都标明了1～1000之间的某个数字，这n张卡片本来是有序的，可是山迪的助手不小心把卡片打乱了。这可急坏了山迪，忙令助手迅速通过一些操作把这些卡片变回有序的，而山迪的助手是个思想简单的人，他能做的操作只有一种：交换任意两张卡片的位置。 现在，山迪想知道助手最少交换几次可以达到目的，以便尽快决定是否替换这个魔术表演，聪明的你能帮助他么？ 输入格式：第1行是一个正整数n，第2行n个是打乱顺序后、每张卡片上的数字。 输出格式：输出所需要的最少交换次数 输入样例： 5 1 4 7 8 3 输出样例： 3 C++

这是一个求解逆序对数量的问题。在一个序列中，如果有两个数 a[i] 和 a[j]，i < j 且 a[i] > a[j]，那么这两个数就构成了一个逆序对。

我们可以使用归并排序来求解逆序对数量，具体做法是在归并的过程中统计逆序对数量。假设左半部分和右半部分已经分别有序，我们可以使用双指针分别指向左半部分和右半部分的起始位置，比较两个指针所指的元素大小，如果左半部分的元素更大，则说明右半部分的所有元素都比它小，因此逆序对数量增加了右半部分的长度；如果右半部分的元素更大，则说明左半部分的所有元素都比它大，因此逆序对数量增加了左半部分剩余元素的数量。具体实现可以参考下面的代码：

#include <iostream>
using namespace std;

const int N = 110;

int n;
int a[N], tmp[N];

// 统计跨越左右两个部分的逆序对数量
int merge(int l, int r) {
    if (l >= r) return 0;

    int mid = l + r >> 1;
    int cnt = merge(l, mid) + merge(mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            cnt += mid - i + 1;  // 统计逆序对数量
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];

    for (int i = l, j = 0; i <= r; i++, j++) {
        a[i] = tmp[j];
    }

    return cnt;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int cnt = merge(0, n - 1);

    cout << cnt << endl;

    return 0;
}

输入样例：

5
1 4 7 8 3

输出样例：

3