51Nod--1019 逆序数

柔光的暖阳◎ 2022-06-14 09:20 192阅读 0赞

题目链接：[http://www.51nod.com/onlineJudge/questionCode.html\#!problemId=1019][http_www.51nod.com_onlineJudge_questionCode.html_problemId_1019]

基准时间限制：1 秒 空间限制：131072 KB

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。  
如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。给出一个整数序列，求该序列的逆序数。  
Input  
第1行：N，N为序列的长度（n <= 50000)  
第2 - N + 1行：序列中的元素（0 <= A\[i\] <= 10^9）  
Output  
输出逆序数  
Input示例  
4  
2  
4  
3  
1  
Output示例  
4

逆序数，根据题目意思很适合用冒泡排序，事实上冒泡排序思想确实可以解决，只是时间复杂度偏高O(n^n) ，对这道题的数据来说肯定不能过全部的数据。我们这里还可以采用归并排序的思想，归并排序的思想小伙伴们可以参考一下这篇文章：[http://blog.csdn.net/hacker\_zhidian/article/details/61616342][http_blog.csdn.net_hacker_zhidian_article_details_61616342]

下面给出代码：

#include <iostream>
    #include <stdio.h>
    using namespace std;
    const int N = 50010;
    int a[N];
    int b[N];
    int sum = 0;
    
    // 合并左右两边的数组元素，数组元素的交换在这里进行 
    void merge(int left, int mid, int right) {
        int i = left;
        int j = mid+1;
        int index = 0;
        // 进行左右两边的元素合并 
        for(; i <= mid && j <= right; ) {
            if(a[i] <= a[j]) { // 从小到大排序 
                b[index++] = a[i++];
            } else {
                b[index++] = a[j++];
                sum += mid-i+1; // 逆序数增加，这里是核心代码 
            }
        }
        // 当有一边中的元素全部用完之后，将剩下的那一边元素直接复制 
        while(i <= mid) {
            b[index++] = a[i++];
        }
        while(j <= right) {
            b[index++] = a[j++];
        }
        // 将合并好了的数组元素复制到原来的数组中 
        for(int k = 0; k < index; k++) {
            a[left++] = b[k];
        }
    }
    
    // 递归进行反复合并，实现排序，数组下标范围：[left, right] 
    void mergeSort(int left, int right) {
        // 当剩下的未合并的元素至少为两个的时候，合并这两个元素
        if(left < right) { 
            int mid = (right + left) / 2;
            mergeSort(left, mid);
            mergeSort(mid+1, right);
            merge(left, mid, right);
        }
    }
    
    int main() {
        int n;
        cin >> n;
        for(int i = 0; i < n; i++) {
            scanf("%d", a+i);
        }
    
        mergeSort(0, n-1);
    
        cout << sum << endl;
    
        return 0;
    }

[http_www.51nod.com_onlineJudge_questionCode.html_problemId_1019]: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1019
[http_blog.csdn.net_hacker_zhidian_article_details_61616342]: http://blog.csdn.net/hacker_zhidian/article/details/61616342