救救孩子吧！TLE！QAQ

20110915_260 @ 2024-03-17 09:28:27

#include<iostream>
#include<algorithm>
using namespace std;
int a[500005];
int n,sum;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            if(a[i]>a[j])
                sum++;
        }
    }
    printf("%d",sum);
    return 0;
}

by kevinZ99 @ 2024-03-17 09:31:42

@20110915_260

严格的说是\frac{n^{2}}{2}但却是超时，所以请使用 O(nlogn) 的归并排序

by YuYuanPQ @ 2024-03-17 09:31:50

@20110915_260 看一下数据范围 n≤5×10^5

by QWQ_HY_DFX @ 2024-03-17 09:32:01

这怎么救啊，你这O(n^2)肯定\LARGE\text{T}飞啊

正解归并排序或树状数组，都是O(n \log n)

by QWQ_HY_DFX @ 2024-03-17 09:32:17

@20110915_260

by WydnksqhbD @ 2024-03-17 09:49:06

@20110915_260 您好，您目前使用的算法复杂度为 O(n^2)，由于 n\le5\times10^5，这个算法是无法通过的。

正解是归并排序，您可以移步至题解区。归并排序的复杂度为 O(n\log n)，是本题正解。

by l_sbh_rx @ 2024-11-25 20:04:03

用归并排序，这个O(n²)能让你T