求助!!!

P1908 逆序对

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 yoimiya_op @ 2023-08-23 20:59:59

@kun_shuo 其实就相当于数为1 2 3 4 下标为1 2 3 4 求有几个数4-1+1=4


by LuoYuanShiTouLang @ 2023-08-23 21:00:38

@xgop 哎,对对对


by long_ji @ 2023-08-23 21:01:10

@kun_shuo 归并排序是将序列分为极小的一个数一个数然后再去排序,现在你要在排序里面查找逆序对并且用的是右下标减左下标肯定是会少算了第一个数的

为什么他是逆序对的个数

因为h1一定小于h2,满足了i<j 这个条件,接下来你只需要满足a[i]>a[j]就可以了

然后你的a[h1]>a[h2]了肯定满足了逆序对的要求,并且h1在你现在求的序列最左边,h2在最右边,而且这个序列是有序的,所以这个序列将会全部满足逆序对


by long_ji @ 2023-08-23 21:01:57

所以用mid-h1+1


上一页 |