题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

隐含递归终止条件写法

时间复杂度分析：blablabla

C++ 代码

#include <stdio.h>
#include <iostream>
#define N 100010
using namespace std;
int a[N];
int temp[N];
long long mergesort(int l,int r)
{
    int i,j,k=0;
    long long sum=0;
    int mid=(l+r)/2;
    if(l<r) //当区间的长度大于1时，不断进行区间划分
    {
        sum=mergesort(l,mid)+mergesort(mid+1,r);
    }


    for(i=l,j=mid+1;i<=mid&&j<=r;)
    {
        if(a[i]<=a[j])  //非逆序
        {
            temp[k++]=a[i++];
        }
        else //逆序
        {
            sum+=mid-i+1;   //统计a[l..mid]中的逆序数量
            temp[k++]=a[j++];

        }
    }
    for(;i<=mid;)
    {
        temp[k++]=a[i++];
    }
    for(;j<=r;)
    {
        temp[k++]=a[j++];
    }
    for(i=l,j=0;j<k;i++,j++)
    {
        a[i]=temp[j];
    }
    return sum;
}

int main()
{
    int n,i;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    cout<<mergesort(0,n-1);

}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla