50分归并代码求调

P1908 逆序对

___wa___ @ 2023-04-11 20:10:14

rt,用裸的归并排序改了改,WA了后10个点

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

数组肯定开的够大了吧...


by Ruiqun2009 @ 2023-04-11 20:22:17

@wa long long.


by ___wa___ @ 2023-04-11 20:22:59

@Ruiqun2009 谢(


|