编辑代码

#include <stdio.h>

// 合并两个子数组并计算逆序对
long long merge(int arr[], int temp[], int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int k = left;
    long long inversions = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            // 如果arr[i] > arr[j]，那么arr[i]到arr[mid]之间的元素都与arr[j]构成逆序对
            inversions += (mid - i + 1);
            temp[k++] = arr[j++];
        }
    }

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

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

    for (int x = left; x <= right; x++) {
        arr[x] = temp[x];
    }

    return inversions;
}

// 计算逆序对数目并排序数组
long long countAndSort(int arr[], int temp[], int left, int right) {
    long long inversions = 0;

    if (left < right) {
        int mid = (left + right) / 2;

        // 递归地计算左半部分和右半部分的逆序对数目
        inversions += countAndSort(arr, temp, left, mid);
        inversions += countAndSort(arr, temp, mid + 1, right);

        // 合并两个子数组并计算逆序对数目
        inversions += merge(arr, temp, left, mid, right);
    }

    return inversions;
}

int main() {
    int n;
    printf("请输入整数的个数: ");
    scanf("%d", &n);

    if (n <= 0) {
        printf("无效的输入。\n");
        return 1;
    }

    int arr[n];
    int temp[n];

    printf("请输入%d个整数, 以空格隔开: ", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    int value;
    while (1) {
        scanf("%d", &value);
        if (value == -1) {
            break;
        }
    }

    long long inversions = countAndSort(arr, temp, 0, n - 1);

    printf("逆序对数目为: %lld\n", inversions);

    return 0;
}