归并排序TLE（QWQ）

iamsh @ 2024-01-14 11:06:11

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5; 
int  n,a[N],f[N];
long long ans;
void merge_sort(int l,int r) {
    if(l == r) {
        return ; 
    }
    int mid = (l + r) >> 1;
    merge_sort(1,mid);
    merge_sort(mid + 1,r);
    int i = l,j = mid + 1,cnt = l;
    while(i <= mid && j <= r) {
        if(a[i] <= a[j]) {
            f[cnt ++] = a[i ++];
        }
        else {
            f[cnt ++] = a[j ++];
            ans += mid + 1 - i;
        }
    }
    while(i <= mid) {
        f[cnt ++] = a[i ++];
    }
    while(j <= r) {
        f[cnt ++] = a[j ++];
    }   
    for(int i = l;i <= r;i ++)
    {
        a[i] = f[i];
    }
}
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d",&a[i]);
    }
    merge_sort(1,n);
    printf("%d",ans);
    return 0;
}

by ICE__LX @ 2024-01-14 11:36:06

也可以这么写哦~

void binary_search(long long le,long long ri){
    if(le==ri) return;//当只有一个数不需要排序(子序列递归达到最深层数) 

    int mid=(le+ri)/2;//将序列二分
    int i=le,j=mid+1,k=le;//指针k控制代存数组r的定位赋值 
    while(i<=mid&&j<=ri){
    //枚举每组首个数 
        if(a[i]<=a[j]) r[k]=a[i],k++,i++;
        else r[k]=a[j],k++,j++;
    //判断大小，并执行赋值，跳过已枚举过的数，指针指向下一位数      
    }

    //将代存数组r补全 
    while(i<=mid) 
     r[k]=a[i],k++,i++;
      while(j<=ri)
       r[k]=a[j],k++,j++;

    //转存到原数组a 
    for(int i=le;i<=ri;i++)
    a[i]=r[i];

    return;//结束栈空间 
}

void mergesort(long long le,long long ri) {
    if(le>=ri) return;//序列递归达到最深层数

    int mid=(le+ri)/2;
     mergesort(le, mid);//先给左子序列排序。
      mergesort(mid+1,ri);//再给右子序列排序。
       binary_search(le,ri);//补全数组
}

by ICE__LX @ 2024-01-14 11:39:28

嗯，忘求逆序对了

void binary_search(long long le,long long ri){
    if(le==ri) return;//当只有一个数不需要排序(子序列递归达到最深层数) 

    int mid=(le+ri)/2;//将序列二分
    int i=le,j=mid+1,k=le;//指针k控制代存数组r的定位赋值 
    while(i<=mid&&j<=ri){
    //枚举每组首个数 
        if(a[i]<=a[j]) r[k]=a[i],k++,i++;
        else r[k]=a[j],k++,j++，ans += mid + 1 - i;;
    //判断大小，并执行赋值，跳过已枚举过的数，指针指向下一位数      
    }

    //将代存数组r补全 
    while(i<=mid) 
     r[k]=a[i],k++,i++;
      while(j<=ri)
       r[k]=a[j],k++,j++;

    //转存到原数组a 
    for(int i=le;i<=ri;i++)
    a[i]=r[i];

    return;//结束栈空间 
}

void mergesort(long long le,long long ri) {
    if(le>=ri) return;//序列递归达到最深层数

    int mid=(le+ri)/2;
     mergesort(le, mid);//先给左子序列排序。
      mergesort(mid+1,ri);//再给右子序列排序。
       binary_search(le,ri);//补全数组
}

by Luke_li @ 2024-01-14 11:45:20

打错了一个字

merge_sort(1,mid);

应该是

merge_sort(l,mid);

by Luke_li @ 2024-01-14 11:47:59

@Luke_li 一开始没看出来，调了半天（

by cyx012113 @ 2024-02-06 18:42:21

@Luke_li

我刚也犯了这个错误，还找大佬修复呢！

我也全 TLE 了