蒟蒻求助

P1908 逆序对

sxyn @ 2020-07-27 10:36:28

不知道哪里出错了。。求指导

#include<iostream>
#include<cstdio>
using namespace std;
long long n,a[22233333],b[22233333],ans=0;
long long nxd(int l,int r)
{
    if(l==r) return 0;
    int m=(l+r)/2;
    ans=nxd(l,m)+nxd(m+1,r);
    int p1=l,p2=m+1;
    for(int i=l;i<=r;i++)
    {
        if(p1>m)
        {
            b[i]=a[p2];
            p2++;
        }
        else if(p2>r)
        {
            b[i]=a[p1];
            p1++;
        }
        else if(a[p1]<b[p2])
        {
            b[i]=a[p1];
            p1++;
        }
        else 
        {
            b[i]=a[p2];
            p2++;
            ans+=m-p1+1;
        }
    }
    for(int i=l;i<=r;i++)
        a[i]=b[i];
    return ans;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    cout<<nxd(1,n)<<endl;
    return 0;
}

by 德克萨斯 @ 2020-07-27 10:37:21

同校打卡


by yangzhiqin @ 2020-07-27 10:44:00

同校打卡


by Caicz @ 2020-07-27 10:44:58

换种方法求?(例如树状数组)


by vzyx @ 2020-07-27 11:05:29

@sxyn

   else if(a[p1]<b[p2])

这一行,不是应该和a[p2]比吗

而且两数相等的情况应该是不产生逆序对的,但你的代码里两数相等算到

else 
        {
            b[i]=a[p2];
            p2++;
            ans+=m-p1+1;
        }

这种情况里,就产生逆序对了

另外,数组不要随便开


by sxyn @ 2020-07-27 11:29:07

@vzyx 请问,等于的情况应该算到哪里呢?(30分)


by vzyx @ 2020-07-27 14:13:42

@sxyn

题中说:

逆序对就是序列中 ai > aj,且i < j 的有序对

举例

3

5 5 5

这个序列中显然没有满足上述条件的数对,所以应该输出0,也就是没有逆序对


by sxyn @ 2020-07-28 07:59:03

@vzyx 十分感谢!


|