蒟蒻求助..写了归并还是TLE

P1908 逆序对

Cheney_Z @ 2021-02-01 11:21:05

#include<bits/stdc++.h>
#define int long long
#define Please return
#define AC 0
using namespace std;
const int size = 5e5+10;

inline int read(){
    int x = 0 , f = 1; char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        x = (x<<1) + (x<<3) + ch - 48;
        ch = getchar();
    }
    return x * f;
}

int n,cnt;
int a[size],b[size];

void work(int l,int mid,int r){
    memset(b,0,sizeof(b));
    int i = l , j = mid+1;

    for(int k=l;k<=r;++k){
        if(i>mid) b[k] = a[j++], cnt += mid-i+1;
        else if(j>r) b[k] = a[i++]; 
        else if(a[i] <= a[j]) b[k] = a[i++];
        else b[k] = a[j++],cnt += mid - i + 1;
    }

    for(int k=l;k<=r;++k) a[k] = b[k];
    return;
}

void mysort(int l,int r){
    if(l == r) return;

    int mid = (l+r) >> 1;

    mysort(l,mid);
    mysort(mid+1,r);

    work(l,mid,r);
    return;
}

signed main(){
    n = read(); 
    cnt = 0;

    for(int i=1;i<=n;++i) a[i] = read();
    mysort(1,n);

    printf("%lld\n",cnt);

    Please AC;
}

by Cheney_Z @ 2021-02-01 11:21:39

是归并有问题吗


by Terrible @ 2021-02-01 11:31:07

memset(b,0,sizeof(b));

重复清空多次,复杂度接近O(n^2)

实际上不需要保证数组是空的,只要覆盖掉原来数据就好了,也调不出来原来的数据吧。


by 林聪 @ 2021-02-01 11:57:53

@Terrible 估计复杂度接近O(n^2log n)了


by Terrible @ 2021-02-01 12:08:54

一个16长的数组归并:

[1,16]
[1,8][9,16]
[1,4][5,8][9,12][13,16]
[1,2][3,4][5,6][7,8][9,10][11,12][13,14][15,16]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

排除l==r的情况,work调用次数为:

1+2+4+8=15=16-1

当n充分大的时候调用次数约是n次


by Terrible @ 2021-02-01 12:12:50

n=2^k (k\in N)

\sum_{i=0}^{(\log_2 n )-1} 2^i=n-1

@林聪


by 林聪 @ 2021-02-01 15:30:00

@Terrible 哦确实,我直接用归并复杂度×n了


by Cheney_Z @ 2021-02-01 17:14:58

@Terrible @林聪 去掉memset就AC了 跪谢二位dalao


|