为什么会TLE???

P1908 逆序对

liyifanglan @ 2024-07-14 18:12:48

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    int ans = 0;
    for (int i = 0;i < n; i++){
        for (int j = i+1; j < n; j++){
            if (a[i] > a[j]) ans++;
        }
    }
    printf("%d", ans);
    return 0;
}

by wangruiqi36 @ 2024-07-14 18:22:07

@xd23lyfl

数据范围,n<=500000


by liyifanglan @ 2024-07-14 18:24:14

@wangruiqi36 那怎么办?


by wangruiqi36 @ 2024-07-14 18:26:42

@liyifanglan 可以分治


by lby_commandBlock @ 2024-07-26 19:06:34

@liyifanglan n \leq 10^5 建议归并排序


|