归并排序这样写为什么才30分
  • 板块P1908 逆序对
  • 楼主kcy31
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/7 16:05
  • 上次更新2024/8/7 16:10:08
查看原帖
归并排序这样写为什么才30分
1283132
kcy31楼主2024/8/7 16:05

归并排序这样写为什么才30分

#include <bits/stdc++.h>
using namespace std;
const int N=500010;
int a[N],b[N];
long long ret;
void f(int l,int r){
    if(l==r){
        return;
    }
    int mid=(l+r)/2;
    f(l,mid);f(mid+1,r);
    int i=l,j=mid+1,tot=l;
    while(i<=mid&&j<=r){
        if(a[i]<a[j]){
            b[tot++]=a[i];i++;
        }
        else{
            ret+=mid-i+1;
            b[tot++]=a[j];j++;
        }
    }
    while(i<=mid) b[tot++]=a[i++];
    while(j<=r) b[tot++]=a[j++];
    for(int i=l;i<=r;i++){
        a[i]=b[i];
    }
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    f(1,n);
    cout<<ret;
    return 0;
}
2024/8/7 16:05
加载中...