全部tle,写的归并,希望有大佬指点一下

P1908 逆序对

bingnoi @ 2021-03-17 22:44:57

#include<bits/stdc++.h>
using namespace std;
int number[500005];
int copy_array[5000005];
long long int ans=0;
int total;
//int read(){
//  int acc=0,sign=1;
//  char ch=getchar();
//  while(ch<'0'&&ch>'9'){
//      if(ch=='-'){
//          sign=-1;
//          ch=getchar();
//      }   
//  }
//  while(ch>='0'&&ch<='9'){
//      acc=acc*10+ch-'0';
//      ch=getchar();
//  }
//  return acc*sign;
//}
void msort(int left,int right){
    printf("%d,%d\n",left,right);
    if(left==right)
        return;
    int mid=(left+right)/2;
    int reme_left=left;
    int reme_right=mid+1;
    int array_start=left;
    msort(1,mid);
    msort(mid+1,right);
    while(reme_left<=mid&&reme_right<=right){
        if(number[reme_left]<=number[reme_right])
            copy_array[array_start++]=number[reme_left++];
        else{
            copy_array[array_start++]=number[reme_right++];
            ans+=mid-reme_left+1;
        }
    }
    while(reme_left<=mid)
        copy_array[array_start++]=number[reme_left++];
    while(reme_right<=right)
        copy_array[array_start++]=number[reme_right++];
    for(int m=left;m<=right;m++)
        number[m]=copy_array[m];
}
int main()
{
    //freopen("test.txt","r",stdin);
    scanf("%d",&total);
    for(int m=1;m<=total;m++){
        scanf("%d",&number[m]);
    }
    msort(1,total);
    printf("%lld",ans);
    return 0;
}

by ud2_ @ 2021-03-17 23:09:17

@bingnoi

msort(1,mid);


by bingnoi @ 2021-03-18 10:28:38

@sjx233_ ?请问大佬什么意思


by ud2_ @ 2021-03-18 10:31:18

@bingnoi 这行错了。


by bingnoi @ 2021-03-18 12:13:57

@sjx233_ 大意了 谢谢


|