归并全R!E! 求助！！！

Jiangzhinan @ 2022-01-24 11:56:36

#include <bits/stdc++.h>
using namespace std;
int n,a[100],b[100];
int m;
int solve(int l,int r){
    if(l>=r) return 0;
    int p=(l+r)/2;
    int res=solve(l,p)+solve(p+1,r);
    int i=l,j=p+1,k=l;
    while(k<=r){
        if(j>r||(i<=p&&a[i]<=a[j])){
            b[k++]=a[j++];
        }else{
            res+=p-i+1;
            b[k++]=a[j++];
        }
    }
    for(int i=1;i<=r;++i) a[i]=b[i];
    return res; 
}
int main () {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) cin>>a[i];
    m=solve(1,n);
    printf("%d",&m);
    return 0;
}

by Elgo87 @ 2022-01-24 11:58:31

数组开太小了......

by Jiangzhinan @ 2022-01-24 12:01:29

@Elgo87 谢谢！！！

by Jiangzhinan @ 2022-01-24 12:04:36

#include<bits/stdc++.h>
using namespace std;
long long n,ans,a[500010],c[500010];
void msort(int b,int e)
    {
    if(b==e)
        return;
    int mid=(b+e)/2;
    int i=b;
    int j=mid+1;
    int k=b;
    msort(b,mid);
    msort(mid+1,e);
    while(i<=mid&&j<=e)
        {
        if(a[i]<=a[j])
            c[k++]=a[i++];
        else
            {
            c[k++]=a[j++];
            ans+=mid-i+1;
            }
        }
    while(i<=mid)
        c[k++]=a[i++];
    while(j<=e)
        c[k++]=a[j++];
    for(int l=b;l<=e;l++)
        a[l]=c[l];
    return;
    }
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    msort(1,n);
    printf("%lld\n",ans);
    return 0;
}

by Jiangzhinan @ 2022-01-24 12:05:09

@Jiangzhinan 对了！！！好耶！！！