求排列的逆序数

最新推荐文章于 2022-07-07 19:18:08 发布

与慕

最新推荐文章于 2022-07-07 19:18:08 发布

阅读量8.1k

点赞数 3

分类专栏：一天一块钱

本文链接：https://blog.csdn.net/qq_36664799/article/details/88635695

版权

一天一块钱专栏收录该内容

5 篇文章

订阅专栏

博客围绕求1到n排列的逆序数展开，介绍了逆序数概念，指出逆序数越大与原始排列差异度越大。给出求解注意点，需利用二分归并排序算法（分治），结果用long long存储，还附上了相应的C语言代码。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

openjudge011

题目：

一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。显然，由1,2,…,n 构成的所有n!个排列中，最小的逆序数是0，对应的排列就是1,2,…,n；最大的逆序数是n(n-1)/2，对应的排列就是n,(n-1),…,2,1。逆序数越大的排列与原始排列的差异度就越大。

现给定1,2,…,n的一个排列，求它的逆序数。

注意点：

1. 利用二分归并排序算法（分治）；
2. 注意结果可能超过int的范围，需要用long long存储。

样例输入：

6
2 6 3 4 5 1

输出：

⭐用归并排序，注意数组的范围。

#include<stdio.h>
long long a[100001];
long long b[100001];
long long n;
long long count=0;//计数
void M(long long a[],int start,int mid,int end,long long b[])//降序
{
   int r=0;
   int pa=start;
   int pb=mid+1;

       while(pa<=mid&&pb<=end)
       {
           if(a[pa]>=a[pb])
           {
               b[r++]=a[pa++];
               count=count+end-pb+1;
           }

           else
           {
               b[r++]=a[pb++];

           }

       }
       while(pa<=mid)
       b[r++]=a[pa++];
       while(pb<=end)
       b[r++]=a[pb++];

   for(int i=0;i<end-start+1;i++)
   a[start+i]=b[i];

}
void Msort(long long a[],int start,int end,long long b[])
{
   if(start<end)
   {
       int mid=start+(end-start)/2;
Msort(a,start,mid,b);
Msort(a,mid+1,end,b);
M(a,start,mid,end,b);
   }

}
int main()
{
   scanf("%lld",&n);
   for(long long i=0;i<n;i++)
   {
       scanf("%lld",&a[i]);
   }
   Msort(a,0,n-1,b);
   printf("%lld",count);
   return 0;
}