九度oj 题目1348：数组中的逆序对

题目描述：: 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

输入：: 每个测试案例包括两行：

第一行包含一个整数n，表示数组中的元素个数。其中1 <= n <= 10^5。

第二行包含n个整数，每个数组均为int类型。

输出：: 对应每个测试案例，输出一个整数，表示数组中的逆序对的总数。

样例输入：

4
7 5 6 4

样例输出：

5

一开始用最简单的方法来做，果然超时了

 1 #include <cstdio>
 2 int n;
 3 int num[100002];
 4 
 5 int main(int argc, char const *argv[])
 6 {
 7     while(scanf("%d",&n) != EOF) {
 8         for(int i = 0; i < n; i++) {
 9             scanf("%d",&num[i]);
10         }
11         int cnt = 0;
12         for(int i = 0; i < n-1; i++) {
13             for(int j = i+1; j < n; j++) {
14                 if(num[i] > num[j]) {
15                     cnt++;
16                 }
17             }
18         }
19         printf("%d
",cnt);
20     }
21     return 0;
22 }

之后苦思冥想不知道怎么做，看了看别人的方法，原来是用归并排序

代码如下

 1 #include <cstdio>
 2 typedef long long ll;
 3 
 4 int n;
 5 int num[100002];
 6 int temp[100002];
 7 ll ans = 0;
 8 
 9 
10 void merge(int f1, int e1, int f2, int e2) {
11     int p = 0;
12     int i = f1, j = f2;
13     while(i <= e1 && j <= e2) {
14         if(num[i] > num[j]) {
15             ans = ans + e2 - j + 1;
16             temp[p++] = num[i];
17             i++;
18         }
19         else {
20             temp[p++] = num[j];
21             j++;
22         }
23     }
24     while(i <= e1) {
25         temp[p++] = num[i]; i++;
26     }
27     while(j <= e2) {
28         temp[p++] = num[j]; j++;
29     }
30     for(int i = f1; i <= e2; i++) {
31         num[i] = temp[i-f1];
32     }
33 }
34 
35 int mergeSort(int from, int to) {
36     if(from < to) {
37         int mid = (from + to)/2;
38         mergeSort(from, mid);
39         mergeSort(mid+1,to);
40         merge(from,mid,mid+1,to);
41         
42     }
43     
44 }
45 
46 int main(int argc, char const *argv[])
47 {
48     while(scanf("%d",&n) != EOF) {
49         for(int i = 0; i < n; i++) {
50             scanf("%d",&num[i]);
51         }
52         ans = 0;
53         mergeSort(0, n-1);
54         
55         printf("%lld
",ans);
56     }
57     return 0;
58 }

如果前后两个都有序，那么对于前一个的任意元素，只要找到它大于第二个的某个元素

那么逆序对就会多（15行）

e2 - j + 1个