求助

P1908 逆序对

lizichang @ 2021-09-07 22:38:45

#include<bits/stdc++.h>
using namespace std;
int a[500005],c[500005],n;
long long ans=0;
void m(int l,int r)
{
    if(l==r)    return ;
    int mid=(l+r)/2;
    int i=l,j=mid+1,k=r;
    m(l,mid);
    m(mid+1,r); 
    while(i<=mid&&j<=r)
        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<=l)     c[k++]=a[j++];
    for(int x=l;x<=r;x++)   a[x]=c[x];
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)   scanf("%d",&a[i]);
    m(1,n);
    printf("%lld",ans);
    return 0;
}

by cyhyyds @ 2021-09-07 22:42:11

while(j<=l)


by lizichang @ 2021-09-07 22:47:41

该改了之后,似乎还不对


by lizichang @ 2021-09-08 20:47:21

#include<bits/stdc++.h>
using namespace std;
long long a[500005],c[500005],n;
long long ans=0;
void m(int l,int r)
{
    if(l==r)    return ;
    int mid=(l+r)/2;
    int i=l,j=mid+1,k=r;
    m(l,mid);
    m(mid+1,r); 
    while(i<=mid&&j<=r)
    {
        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<=r)
        c[k++]=a[j++];
    for(int p=l;p<=r;p++)
        a[p]=c[p];
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)   scanf("%lld",&a[i]);
    m(1,n);
    printf("%lld",ans);
    return 0;
}

哪里出问题了??


|