题目描述

blablabla

样例

#include <iostream>
using namespace std;
const int N = 1e6+10;
int n;
unsigned long result = 0;
int q[N], tmp[N];
void quick_sort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int mid = (l + r) / 2;
    int i = l;
    int j = mid + 1;
    quick_sort(q, l, mid);
    quick_sort(q, mid + 1, r);
    int k = 0;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        if (q[i] > q[j]) {result+=(mid-i+1);tmp[k++] = q[j++];}
        //因为指针j所在数列相比指针i所在序列是在后面的，
        如果j指针对应的数小于i指针的数，
        就需要计算i序列中剩余的数（因为剩余的数都大于此时j对应的数
        ，也相当于计算让j对应的数依次往前换位的次数），
        而且每次排序不影响其他的未排序的元素位置，
        这样就可以计算总体的逆序对数。
    }
    while (i <= mid){tmp[k++] = q[i++];}
    while (j <= r)tmp[k++] = q[j++];
    for (i = l,j = 0; i <= r; i++,j++)q[i] = tmp[j];
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &q[i]);
    }
    quick_sort(q, 0, n - 1);
        // for (int i = 0; i < n; i++)
        // {
        //     printf("%d ", q[i]);
        // }
        cout<<result;

return 0;
}

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla