归并排序,50分,求解

P1908 逆序对

Risty @ 2020-03-16 16:30:10

#include<iostream>
#include<cstdio>
using namespace std;
long long a[500000],b[500000];
long long num=0;
void merge(int l,int r){
    if(l>=r)
        return;
    int m=(l+r)/2;  
    merge(l,m);
    merge(m+1,r);
    int k=l,i=l,j=m+1;
    while(i<=m&&j<=r){
        if(a[i]<=a[j])
            b[k++]=a[i++];
        else{
            b[k++]=a[j++];
            num+=m-i+1;
        }
    }
    while(i<=m){
        b[k++]=a[i++];
    }
    while(j<=r){
        b[k++]=a[j++];
    }
    for(int i=l;i<=r;i++)
        a[i]=b[i];

}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    merge(1,n);
    printf("%lld",num);
    return 0;
}

错误信息显示的是on line 1 column 1,read 9,expect 6;两个数组改成int类型就显示on line 1 column 1,read 5,expect 6,求助


by liqingyang @ 2020-03-16 16:34:57

逆序对加反了吧?


by Jmakers @ 2020-08-01 22:37:04

数组分配的容量不够大,你变容量为5e6就可以了


|