归并做的过不了,求救

P1908 逆序对

比尔008 @ 2021-04-30 14:28:54

代码

#include<bits/stdc++.h>
using namespace std;
long long a[500005],b[500005],sss=0;
void gb(int l,int r)
{
    if(l==r) 
      return;
    long long m=(l+r)/2,i=l,j=m+1,k=l;
    gb(l,m);
    gb(m+1,r);
    while(i<=m&&j<=r)
    {
        if(a[i]<a[j]) 
        {
          b[k++]=a[i++];
        }
        else 
        {
          b[k++]=a[j++];
          sss=sss+m-l+1;
        }
    }
    for(;i<=m;i++) 
      b[k++]=a[i];
    for(;j<=r;j++) 
      b[k++]=a[j];
    for(i=l;i<=r;i++) 
      a[i]=b[i];
}
int main()
{ 
    long long n,m,p;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    gb(1,n);
    cout<<sss;
    return 0;
}

by chen_qian @ 2021-04-30 14:39:52

@比尔008 为什么是 m-l+1.。。


by chen_qian @ 2021-04-30 14:41:44

@比尔008 如果你只改那里还是有错。。。还有一个小问题自己找吧


by 比尔008 @ 2021-04-30 14:59:48

@chen_qian 谢谢,已经找到了,边界的问题


|