蒟蒻求助!!望指点
查看原帖
蒟蒻求助!!望指点
546062
黄鱼家的猪楼主2021/9/8 23:47

答案一直算错!!!! 实在是找不到哪里的逻辑差错了,烦请各位佬帮忙看下!感激不尽

#include<stdlib.h>
#include<stdio.h>
#define MAX 500001


int B[MAX];
long long count=0;
void Merge(int A[],int low,int mid,int high){
    int i,j,k;
    for( k = low;k<high;k++){
        B[k]=A[k];  // 复制数组
    }
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
        if(B[i]<=B[j]){
            A[k]=B[i++];
        }
        else{
            A[k]=B[j++];
            count+=mid-i+1;

        }
    }
    while(i<=mid){
        A[k++]=B[i++];
    }
    while(j<=high){
        A[k++]=B[j++];
    }
}

void MergeSort(int A[],int low,int high){
    if(low<high){
    int mid = (high+low)/2;
    MergeSort(A,low,mid);
    MergeSort(A,mid+1,high);
    Merge(A,low,mid,high);
    }
}
int main(){
    int A[MAX];
    int n;
    scanf("%d",&n);
    for(int i =1;i<=n;i++){
        scanf("%d",&A[i]);
    }
    MergeSort(A,1,n);
    printf("%lld",count);
}




2021/9/8 23:47
加载中...