题目描述

逆序对的数量 cpp

样例

// 逆序对的数量
#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int n;
long long ans = 0;
int q[N];
int temp[N];

void reverse_order(int q[],int l,int r)
{
    if (l >= r) return;
    // 左右分治
    int mid = (l + r) / 2;
    reverse_order(q,l,mid);
    reverse_order(q,mid+1,r);
    // 合并左右两个数组
    int i = l, j = mid+1, k = 0;
    while (i <= mid && j <= r)
    {
        if (q[i] > q[j])
        {
            temp[k++] = q[j++];
            ans += (mid - i + 1);
        }
        else
        {
            temp[k++] = q[i++];
        }
    }
    while (i <= mid)
    {
        temp[k++] = q[i++];
    }
    while (j <= r)
    {
        temp[k++] = q[j++];
    }
    // 用temp去更新q
    for (int m=0;m<k;m++)
    {
        q[m + l] = temp[m];
    }

}

int main()
{
    cin >> n;
    for (int i=0;i<n;i++)
    {
        cin >> q[i];
    }
    reverse_order(q,0,n-1);
    cout << ans;
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla