求逆序数（the number of inversions）（数学）

1.用树状数组求逆序数

缺点：只能对整数求逆序数

 1 #include "TreeArray.h"
 2 /*
 3 算法：
 4 由树状数组求逆序对。加入元素i即把以元素i为下标的a[i]值+1，从队尾到队首入队，
 5 每次入队时逆序对数 += getsum(i - 1),即下标比它大的但是值比它小的元素个数。
 6 因为树状数组不能处理下标为0的元素，每个元素进入时+1，相应的其他程序也要相应调整。
 7 求出原始的序列的逆序对个数后每次把最前面的元素移到队尾，逆序对数即为
 8 原逆序对数+比i大的元素个数-比i小的元素个数，因为是0..n,容易直接算出
 9 */
10 int NiXuShu(int Array[], int n)
11 {
12     TreeArray ta(1);
13     ta.clear();
14     int i, sum = 0;
15     for (i = n-1; i >= 0; i --)
16     {
17         ta.modify(Array[i]+1, 1);
18         sum = sum + ta.sum(Array[i]);
19     }
20     return sum;
21 }

View Code

这种方法理解的还不是很透彻，还是要再理解一下。

2.用归并排序求逆序数

缺点：会改变数组中的值

 1 # include <iostream>
 2 # define N 500010
 3 using namespace std;
 4 
 5 long long cnt;
 6 int a[N], t[N];
 7 void merge(int s1, int e1, int s2, int e2)
 8 {
 9     int p1 = s1, p2 = s2, p=0;
10     while(p1 <= e1 && p2 <= e2)
11     {
12         if(a[p1] <= a[p2])
13         {
14             t[p++] = a[p1++];
15         }
16         else
17         {
18             t[p++] = a[p2++];
19             cnt += e1-p1+1;
20         }
21     }
22     while(p1<=e1)
23     {
24         t[p++] = a[p1++];
25     }
26     while(p2 <= e2)
27     {
28         t[p++] = a[p2++];
29     }
30     for(int i = s1; i <= e2; i++)
31     {
32         a[i] = t[i-s1];
33     }
34 }
35 void mergesort(int s, int e)
36 {
37     if(s < e)
38     {
39         int m = (s+e)/2;
40         mergesort(s, m);
41         mergesort(m+1, e);
42         merge(s, m, m+1, e);
43     }
44 }
45 int main(void)
46 {
47     int n;
48     while(cin >> n, n)
49     {
50         cnt = 0;
51         for(int i = 0; i < n; i++)
52             cin >> a[i];
53         mergesort(0, n-1);
54         cout << cnt << endl << endl;
55     }
56 
57     return 0;
58 }

View Code

用cin的话跑时会很多，还是scanf好。