RedWen_shuo @ 2023-08-23 20:21:18
求助,帮我看看哪里出问题了, 我现在还蒙着
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
long long n;
long long a[N];
long long b[N];
long long ans=0;//逆序对的个数
void gsort(long long l,long long r)
{
if(l==r) return;
long long mid=(l+r)/2;
gsort(l,mid); gsort(mid+1,r);
long long h1=l,h2=mid+1,h=l;
while(h1<=mid&&h2<=r)
{
if(a[h1]<=a[h2])
b[h++]=a[h1++];
else{
b[h++]=a[h2++];
ans+=(mid-l+1);
}
}
while(h1<=mid) b[h++]=a[h1++];
while(h2<=r) b[h++]=a[h2++];
for(int i=l;i<=r;i++)
{
a[i]=b[i];
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++){ cin>>a[i];}
gsort(1,n);
// for(int i=1;i<=n;i++)
// {
// cout<<b[i]<<" ";
// }
cout<<ans<<"\n";
return 0;
}
by RedWen_shuo @ 2023-08-23 20:25:28
一直不明白为什么ans+=(mid-h1+1); 能举一个例子吗
by yoimiya_op @ 2023-08-23 20:34:13
@kun_shuo
ans+=(mid-l+1);
把L改成h1就对了;h1是你运用归并排序将最原始的数列分成的碎的数列的左边界,但你用L为什么不对?
你看这一句b[h++]=a[h1++];
h1++;每次h1都是自增的,而你用L则是一直不变的,把这改了就对了(帮你试过了)
by RedWen_shuo @ 2023-08-23 20:35:12
@xgop 一直不明白为什么ans+=(mid-h1+1); 能举一个例子吗
by yoimiya_op @ 2023-08-23 20:35:29
@kun_shuo 再不懂回宿舍给你讲明白点
by yoimiya_op @ 2023-08-23 20:35:47
@kun_shuo 我试试啊
by yoimiya_op @ 2023-08-23 20:45:40
() 先看看
by yoimiya_op @ 2023-08-23 20:49:51
@kun_shuo 懂了吗
by RedWen_shuo @ 2023-08-23 20:55:31
@xgop 我不知道怎么保证 mid-h1+1 一定是逆序对的数量
by yoimiya_op @ 2023-08-23 20:57:52
你等会;张骥给你回呢
by LuoYuanShiTouLang @ 2023-08-23 20:59:29
@kun_shuo 因为a[h1]>a[h2],则h1后面的数也大于h2(因为数组一定有序),mid-h+1求h1及其后面满足逆序对的个数