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 十分感谢!