1 条题解

  • 1
    @ 2022-8-19 17:39:56
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int mod=99999997;
    long long n,x[10000005],p[1000005],ans=0;
    struct fire{
        int hi,bh;
    }l1[1000005],l2[1000005];
    bool cmp1(fire a,fire b)
    {
        return a.hi<b.hi;
    }
    void msort(int s,int t)//归并排序; 
    {
        if(s==t)return ;
        int mid=(s+t)/2;
        msort(s,mid);msort(mid+1,t);
        int i=s,k=s,j=mid+1;
        while(i<=mid && j<=t)
        {
            if(x[i]<=x[j])
            {
                p[k]=x[i];
                ++k;++i;
                
            }
            else
            {
                p[k]=x[j];
                ++k;++j;
                ans=(ans+mid-i+1)%mod;
    			//此处找到逆序对,mid-i~mid中数全都与j构成逆序,还会少算一个,+1;
            }
        }
        while(i<=mid)
        {
            p[k]=x[i];
            ++k;++i;
        }
        while(j<=t)
        {
            p[k]=x[j];
            ++k;++j;
        }
        for(int i=s;i<=t;i++)
        {
            x[i]=p[i];
        }
    }
    int main()
    {
        scanf("%lld",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&l1[i].hi),l1[i].bh=i;
        for(int i=1;i<=n;i++)
            scanf("%d",&l2[i].hi),l2[i].bh=i;
        sort(l1+1,l1+n+1,cmp1);
        sort(l2+1,l2+n+1,cmp1);
        //排序; 
        for(int i=1;i<=n;i++)
            x[l2[i].bh]=l1[i].bh; 
        msort(1,n);
        //调用归并; 
        printf("%lld",ans);
        return 0;//这个不会有人忘的吧? 
    }
    
    • 1

    信息

    ID
    45
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    8
    已通过
    7
    上传者