数组会超时，怎么办？(呼叫dalao答疑解惑)

boshu @ 2021-11-06 19:58:39

by fjy666 @ 2021-11-06 19:59:22

where?

by boshu @ 2021-11-06 20:01:39

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long a[50000],n,sum=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<=n-1;i++){
        for(int j=0;j<=i-1;j++){
            if(a[j]>a[i]){
                sum=sum+1;
            }
    }
}
    cout<<sum;
    return 0;
}

by boshu @ 2021-11-06 20:02:11

@fjy666 不好意思，是萌新，刚刚不知道格式打不出来

by fjy666 @ 2021-11-06 20:03:43

@shenyanghao 您的复杂度是 \mathcal{O}(n^2)，过不了 n = 5\times10^5 的数据，建议学习归并排序再来且此题哦

by fjy666 @ 2021-11-06 20:03:57

@boshu

by qnqfff @ 2021-11-06 20:04:51

这题不是归并排序?用暴力不会T就来了鬼了

by boshu @ 2021-11-06 20:07:33

@fjy666 不知道该怎么办，会超时

by boshu @ 2021-11-06 20:08:16

@fjy666 谢谢dalao了解了

by Yikara @ 2021-11-06 20:08:17

应该不会 O(n^2)过 50 万吧 by chen_zhe

by boshu @ 2021-11-06 20:08:29

@qnqfff 谢谢dalao了解了