求助!!!

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 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及其后面满足逆序对的个数


| 下一页