计算逆序对问题 OJ OJ运行超时：Time Limit Exceeded

Question

问题遇到的现象

OJ运行超时： Time Limit Exceeded

条件

内存限制：64 MiB
时间限制：1000 ms
标准输入输出
题目类型：传统
评测方式：文本比较

题目

题目描述
设A[1..n]是一个包含N个数的数组。如果在i〈 j的情况下，有A[i] 〉a[j]，则(i,j)就称为A中的一个逆序对。
使用 归并排序 可以用O(nlogn)的时间解决统计逆序对个数的问题 。
输入格式
第1行：1个整数N表示排序元素的个数。(1≤N≤100000) 第2行：N个用空格分开的整数，每个数在小于100000
输出格式
1行：仅一个数，即序列中包含的逆序对的个数
样例
样例输入
3
1 3 2
样例输出
1

问题相关代码，请勿粘贴截图

#include <iostream>
using namespace std;
int main()
{
    long long NUM,l = 0,O,P = 0;
    cin >> O;
    int num[O];
    for(int i = 0;i < O;i++)
    {
        cin >> NUM;
        num[i] = NUM;
        for(int v = i - 1;v > -1;v--)
        {
            if(num[i] < num[v])
                P++;
        }
    }
    cout << P;
}

```

运行结果及报错内容

报错0：Exited with return code 0
结果正常
运行超过OJ时间限制

我的解答思路和尝试过的方法

1)定义数组存储集合
2)比对集合中符合条件元素的大小
3)输出

我想要达到的结果

OJ Accept

Answer 1

解决一个问题的第一步是定义清楚问题。

首先我们给出逆序对的定义：
对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对。
重要的地方在于，一个元素可以不只是在一个逆序对中存在。如果 k > j > i 且 a[i] > a[j] > a[k]，那么这里
有两个含 a[i] 的逆序对，分别是 (a[i], a[j]) 和 (a[i], a[k]), a[i]是可以使用多次的。

那么第二步是分析问题，这里我们可以使用分治法解决问题。

我们将序列从中间分开，将逆序对分成三类：

两个元素都在左边；
两个元素都在右边；
两个元素一个在左一个在右；
因此这就是我们算法的大致框架：

计算逆序对的数量（序列）：

1. 递归算左边的；
2. 递归算右边的；
3. 算一个左一个右的；
4. 把他们加到到一起。

这个时候我们注意到一个很重要的性质，左右半边的元素在各自任意调换顺序，是不影响第三步计数的，因此我们可以数完就给它排序。这么做的好处在于，如果序列是有序的，会让第三步计数很容易。
如果无序暴力数的话这一步是O(n^2)的。

比如序列是这样的

4 5 6 | 1 2 3
当你发现 4 比 3 大的时候，也就是说右边最大的元素都小于左边最小的元素，那么左边剩下的5和6都必然比右边的所有元素大，因此就可以不用数5和6的情形了，直接分别加上右半边的元素个数就可以了，这一步就降低到了
O(n), 我们知道递归式 T(n) = 2T(n/2)+O(n) = O(nlogn)的，所以排序的成本是可以接受的，并且这一问题下，
可以很自然地使用归并排序。

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], tmp[N];
LL merge_sort(int q[], int l, int r){
    if (l >= r) return 0;
    int mid = l + r >> 1;
    LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else{
            res += mid - i + 1;
            tmp[k ++ ] = q[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];
    return res;
}
int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    cout << merge_sort(a, 0, n - 1) << endl;
    return 0;
}