归并RE三个点求助！

Danny_SCQ @ 2021-06-19 21:41:32

#include<cstdio>
using namespace std;
int a[40000+5];
int t[40000+5];
int ans=0;
void merge(int A[],int l,int r,int T[])
{
        int mid=(l+r)/2;
        int i=l;
        int j=mid+1;
        int t=l;
        while(i<=mid&&j<=r)
        {
            if(A[i]<A[j])
            {
                T[t++]=A[i++];
            }else{
                ans+=mid-i+1;
                T[t++]=A[j++];
            }
        }
        while(i<=mid)
        {
            T[t++]=A[i++];
        }
        while(j<=r)
        {
            T[t++]=A[j++];
        }
        for(int i=1;i<=r;i++)
        {
            A[i]=T[i];
        }       
}
void mergesort(int A[],int l,int r,int T[])
{
    if(l<r)
    {
        int mid=(l+r)/2;
        mergesort(A,l,mid,T);
        mergesort(A,mid+1,r,T);
        merge(A,l,r,T);
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    mergesort(a,1,n,t);
    printf("%d ",ans);
    return 0;
}

by Wuyanru @ 2021-06-19 22:06:33

数组开小了\

by Danny_SCQ @ 2021-06-21 22:16:54

@卓远YC班吴彦儒 改了啊还是不行

by Wuyanru @ 2021-06-22 13:19:35

@shichengqi 可是你代码打的是 5\times10^4

by Danny_SCQ @ 2021-06-22 22:52:53

@卓远YC班吴彦儒 改了但内存不够了```c

#include<cstdio>
using namespace std;
int a[500005];
int t[500005];
long long ans=0;
void merge(int A[],int l,int r,int T[])
{
        int mid=(l+r)/2;
        int i=l;
        int j=mid+1;
        int t=l;
        while(i<=mid&&j<=r)
        {
            if(A[i]<A[j])
            {
                T[t++]=A[i++];
            }else{
                ans+=mid-i+1;
                T[t++]=A[j++];
            }
        }
        while(i<=mid)
        {
            T[t++]=A[i++];
        }
        while(j<=r)
        {
            T[t++]=A[j++];
        }
        for(int i=l;i<=r;i++)
        {
            A[i]=T[i];
        }       
}
void mergesort(int A[],int l,int r,int T[])
{
    if(l<r)
    {
        int mid=(l+r)/2;
        mergesort(A,l,mid,T);
        mergesort(A,mid+1,r,T);
        merge(A,l,r,T);
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    mergesort(a,1,n,t);
    printf("%lld ",ans);
    return 0;
}

by Wuyanru @ 2021-06-23 12:11:11

你疯狂传入数组肯定会超内存吧