样例过了却还是没过

P1908 逆序对

朕爱学习 @ 2020-01-23 15:59:07

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int Maxn=20201;
ll n,tot,mid;
struct num{
    ll No;
    ll num;
}a[Maxn];

int cmp(const num &x,const num &y)
{
    return x.num<y.num;
}

void nxd(int x,int y)
{
    if(y-x==1||y==x)
    {
        if(a[x].num!=a[y].num&&a[x].No>a[y].No)
        tot++;
        return;
    }
    mid=(x+y)/2;
    for(int i=mid;i<=y;i++)
    {
        for(int j=x;j<mid;j++)
        {
            if(a[i].num!=a[j].num&&a[i].No<a[j].No)
            {
                tot++;
            }
        }
    }
    nxd(x,mid-1);nxd(mid,y);
    return;
}

int main()
{
    scanf("%lld",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i].num);
        a[i].No=i;
    }
    sort(a+1,a+1+n,cmp);
    nxd(1,n);
    printf("%lld",tot);
    return 0;
}

|