归并排序,哪错了

P1908 逆序对

Anakin @ 2019-10-02 13:46:10

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define MAXN 500000+10
using namespace std;
inline int read(){
    int out=0;
    char c=getchar();
    while(c<48||c>57) c=getchar();
    while(c<=57&&c>=48){
        out=(out<<1)+(out<<3)+c-48;
        c=getchar();
    }
    return out;
}
inline void write(ll x){
    if(x>9) write(x/10);
    putchar(x%10+48);
}
int a[MAXN];
ll ans;
void Merge(int a[],int l,int mid,int r){
    int len=r-l+1;
    int *temp=new int[len];
    int i=1,j=mid+1;
    int cnt=0;
    while(i<=mid&&j<=r){
        if(a[i]<=a[j]){
            temp[cnt++]=a[i++];
        }
        else{
            ans+=mid-i+1;
            temp[cnt++]=a[j++];
        }
    }
    for(;i<=mid;++i){
        temp[cnt++]=a[i];
    }
    for(;j<=r;++j){
        temp[cnt++]=a[j];
    }
    for(int k=0;k<len;++k){
        a[l+k]=temp[k];
    }
}
void Mergesort(int a[],int l,int r){
    if(l<r){
        int mid=(l+r)>>1;
        Mergesort(a,l,mid);
        Mergesort(a,mid+1,r);
        Merge(a,l,mid,r);
    }
}
int main(){
    int n=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
    }
    Mergesort(a,1,n);
    write(ans);
    return 0;
}

by 火车司机 @ 2019-10-02 13:57:41

@Anakin Merge函数第三行i的初值赋错了,应该是l


by BFqwq @ 2019-10-02 14:00:49

赋值的锅,应该是从l开始而不是1


|