最小反转数（归并排序求逆序对）

最小反转数

时间限制：2000/1000 MS（Java / Others）内存限制：65536/32768 K（Java / Others）
总投稿数：26297可接受的提交内容：15442
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1394

问题描述

给定数字序列a1，a2，...，an的反转数是满足i <j和ai> aj的对（ai，aj）的数量。

对于给定的数字序列a1，a2，...，a，如果我们将第一个m> = 0个数字移动到seqence的末尾，我们将获得另一个序列。总共n个如下序列：

a1，a2，...，an-1，an（其中m = 0 - 初始序列）
a2，a3，...，an，a1（其中m = 1）
a3，a4，...，an，a1，a2（其中m = 2）
...
an，a1，a2，...，an-1（其中m = n-1）

您被要求编写程序从上述序列中找出最小反转数。

输入

输入包含许多测试用例。每个案例由两行组成：第一行包含正整数n（n <= 5000）; 下一行包含从0到n-1的n个整数的排列。

产量

对于每种情况，在一条线上输出最小反转数。

样本输入

10 1 3 6 9 0 8 5 7 4 2

样本输出

思路：这一题最主要的就是运用到了逆序数的性质，将第一个数移动到最后一个数此时增加了n-a[0]-1个n逆序数，减少了a[0]逆序数（这是为什么呢？首先，这个数在最前面，也就是说后面所有的数的位置都比它大，只需要求原序列第二个到第n个数有几个比第一个大就可以了，由于这里数的范围是0-n-1，所以后面比第一个数小总共有num[0]个数，比它大的有n-a[0]-1），最后求出所有的情况，取最小的逆序数就好了

下面是求逆序数的方法：

在归并排序中求逆序数，其实是在归并过程中，让i作为左边数组的遍历索引，j作为右边数组的遍历索引。在合并的过程中，如果a[i]>b[j]，那么合并之后就会产生mid-i个逆序数对。因为a[i+1],a[i+2],...,a[mid-1]都会大于b[j].

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<vector>
 4 #include<string.h>
 5 using namespace std;
 6 #define LL long long
 7 const int maxn=5050;
 8 int r[maxn],r1[maxn],a[maxn];
 9 LL ans=0;
10 void Merge(int r[], int r1[], int s, int m, int t)
11 {
12     int i=s,k=s;
13     int j=m+1;
14     while(i<=m&&j<=t)
15     {
16         if(r[i]<=r[j])
17             r1[k++]=r[i++];
18         else
19         {
20             r1[k++]=r[j++];
21             ans+=(m-i+1);///记录逆序数，
22         }
23 
24     }
25     while(i<=m)
26         r1[k++]=r[i++];
27     while(j<=t)
28         r1[k++]=r[j++];
29     k=s;
30     while(s<=t)
31         r[s++]=r1[k++];
32 }
33 void MergeSort(int r[],int r1[],int s,int t)
34 {
35     if(s==t)
36         return ;
37     else
38     {
39         int m=(s+t)>>1;
40         MergeSort(r, r1, s, m);///分治
41         MergeSort(r, r1, m+1, t);
42         Merge(r, r1, s, m, t);///合并
43     }
44 
45 }
46 int main()
47 {
48 
49     int n;
50     while(~scanf("%d",&n))
51     {
52     ans=0;
53         for(int i=0; i<n; i++)
54         {
55             scanf("%d",&r[i]);
56             a[i]=r[i];
57         }
58         MergeSort(r,r1,0,n-1);
59         LL answer=ans;
60         for(int i=0; i<n; i++)
61         {
62             ans+=(n-2*a[i]-1);
63             answer=min(ans,answer);
64         }
65         printf("%lld
",answer);
66     }
67 
68 
69     return 0;
70 }