各位大佬帮忙看看哪里错了,后面十个测试点TLE

P1908 逆序对

莫说啥 @ 2019-08-22 16:12:03

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
int nixu(int a[],int m,int l)
{
    if(m==l)
    return 0;
    else if(l-m==1)
    {
        if(a[l]>=a[m])
        return 0;
        else return 1;
    }
    int mid=(m+l)/2;
    vector<int> b;
    vector<int> c;
    for(int i=m;i<=mid;i++)
    {
        b.push_back(a[i]);
    }
    for(int i=mid+1;i<=l;i++)
    {
        c.push_back(a[i]);
    }
    sort(b.begin(),b.end());
    sort(c.begin(),c.end());
    int num=0;
    int t1=b.size()-1,t2=c.size()-1;
    while(t1>=0&&t2>=0)
    {
        if(b[t1]<=c[t2])
        t2--;
        else{
            t1--;
            num+=t2+1;
        }

    }
    return num+nixu(a,m,mid)+nixu(a,mid+1,l);
}
int main()
{    
    int n,a[500005];
   cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    cout<<nixu(a,1,n)<<endl;
    return 0;
}

by fzfnf @ 2019-08-22 16:24:27

@莫说啥 使用归并排序


by Computer1828 @ 2019-08-22 16:26:56

@莫说啥 推荐食用:归并排序求逆序对,值域线段树求逆序对,树状数组求逆序对(其实和线段树没啥区别)


by End_donkey @ 2019-08-22 16:27:46

树状数组


by caidzh @ 2019-08-22 20:16:08

你甚至还可以平衡树求逆序对


|