《双色球》

P1908 逆序对

Li_mz__ @ 2022-11-04 21:26:43

#include <bits/stdc++.h>

using namespace std;
int main(){
    long long n,arr[214748394];
    long long ans = 0;
    scanf("%d",&n);
    for(long long i = 0;i < n;i++){
        scanf("%d",&arr[i]);
    }
    for(long long i = 0;i < n;i++){
        for(long long j = i + 1;j < n;j++){
            if(arr[i] > arr[j]){
                ans++;
            }
            else{
                ans += 0;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

论我为啥一半AC一半TLE


by _Jonny_404 @ 2022-11-04 21:58:38

对于 50\% 的数据,n\le4×10^4


by _Jonny_404 @ 2022-11-04 21:59:56

这题可以进行一个归并排序,在合并时进行判断,由于归并的时间复杂度是 O(n \log n)所以不会超时


by _Jonny_404 @ 2022-11-04 22:01:00

@Li_mz__ 所以第一篇题解和我的方法相同,可以去看一下


by HZHan @ 2022-11-13 21:06:37

暴力还有一半的分?


by HZHan @ 2022-11-13 21:08:21

草,开了O2还真有(


by CooooldWind_ @ 2022-11-28 15:55:27

所以您是觉得程序能在1秒内跑完250,000,000,000次运算???


上一页 |