C++样例过了,但是全WA

P1908 逆序对

Nemo_ @ 2023-07-13 15:13:04

#include<bits/stdc++.h>
using namespace std;
long int p[500010];
long int a[500010];
long long n,sum;
void msort(int s,int t)
{
    if(s==t) return ;
    int mid=(s+t)/2;
    int i=s,j=mid+1,k=s;
    msort(s,mid);
    msort(mid+1,t);
    while(i<=mid&&j<=t)
    {
        if(a[i]<=a[j])
        {
            p[k]=a[i];
            k++;i++;
        }
        else
        {
            p[k]=a[j];
            j++;k++;
            sum+=mid-i+1;
        }
    }
    while(i<=mid)
    {
        p[k]=a[i];
        k++;i++;
    }
    while(j<=t)
    {
        p[k]=a[i];
        k++;j++;
    }
    for(int m=s;m<=t;m++)
    {
        a[m]=p[m];
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    } 
    msort(1,n);
    printf("%lld",sum);
    return 0;
}

by KidzzZip @ 2023-07-14 17:03:32

#include<bits/stdc++.h>
using namespace std;
long long p[500010];
long long a[500010];
long long n,sum=0;
void msort(int s,int t)
{
    if(s>=t) return ;//problem 1 源码:if(s==t) return; 
    int mid=(s+t)/2;
    int i=s,j=mid+1,k=s;
    msort(s,mid);
    msort(mid+1,t);
    while(i<=mid&&j<=t)
    {
        if(a[i]<=a[j])
        {
            p[k]=a[i];
            k++;i++;
        }
        else
        {
            p[k]=a[j];
            j++;k++;
            sum=sum+mid-i+1;
        }
    }
    while(i<=mid)
    {
        p[k]=a[i];
        k++;i++;
    }
    while(j<=t)
    {
        p[k]=a[j];
        k++;j++;
//       源码:k++;j++;
        //problem 2
    }
    for(int m=s;m<=t;m++)
    {
        a[m]=p[m];
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    } 
    msort(1,n);
    printf("%lld",sum);
    return 0;
}

|