蒟蒻求助,归并排序居然TLE了10个点

P1908 逆序对

xeri_chen @ 2019-06-28 17:28:39

可能我的归并不够标准但应该是对的吧。

#include<bits/stdc++.h>

using namespace std;
const int N=100000;

int a[6*N];
long long ans;

void px(int bin,int end)
{
    if(end-bin<=1) return;
    int mid=(bin+end)/2;

    px(bin,mid);
    px(mid,end);
    int s[N]={},n=end-bin,na=bin,nb=mid;
    for(int i=0;i<n;i++)
    {
        if(a[na]>a[nb])
        {
            s[i]=a[nb++];
            ans+=mid-na;
        }
        else
        {
            s[i]=a[na++];

        }
        if(na==mid)
        {
            while(nb!=end)
            {
                s[++i]=a[nb++];

            }
            break;
        }
        if(nb==end)
        {
            while(na!=mid)
            {
                s[++i]=a[na++];

            }
            break;
        }
    }
    na=0;
    for(int i=bin;i<end;i++)
        a[i]=s[na++];
}

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    px(0,n);
    cout<<ans;
    return 0;
}

by Jelly_Goat @ 2019-06-28 17:58:04

@xeri_chen
把辅助数组开到全局就OK了
好像是分配空间的事
这个好像也需要time
我一开始也是TLE


by aminoas @ 2019-06-28 18:04:53

树状数组大法好


by _Sein @ 2019-06-28 18:55:41

@xeri_chen 初始化数组需要时间,相当于memset


by xeri_chen @ 2019-06-28 21:51:44

原来如此,本蒟蒻受教了,谢谢各位大佬


|