SDUT 3402 数据结构实验之排序五：归并求逆序数

数据结构实验之排序五：归并求逆序数

Time Limit: 40MS Memory Limit: 65536KB

Problem Description

对于数列a1,a2,a3…中的任意两个数ai,aj (i < j)，如果ai > aj,那么我们就说这两个数构成了一个逆序对；在一个数列中逆序对的总数称之为逆序数，如数列 1 6 3 7 2 4 9中，(6,4)是一个逆序对，同样还有(3,2),(7,4),(6,2)，(6,3)等等，你的任务是对给定的数列求出数列的逆序数。

Input

输入数据N(N <= 100000)表示数列中元素的个数，随后输入N个正整数，数字间以空格间隔。

Output

输出逆序数。

Example Input

10
10 9 8 7 6 5 4 3 2 1

Example Output

45

DQE:

注意本题坑点！统计逆序数的变量必须要long int 或者long long int ，不然会溢出导致Wrang Anser！
逆序数即为 （ 每次归并时第二序列放置每个元素时第一序列剩余元素个数之和 ） 之和，参见代码内注释~
归并排序思想类似快排，代码逻辑简明易理解。
动态申请内存new确实比提前定义好数组直接使用耗时短，必要时用空间换时间！

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 int f[100010],n;    //!0　　//如下所述temp在这里一同定义
 6 long int count;    //注意本题坑点！计数变量用int会溢出导致Wrong Anser！long可AC，还不行的话就long long！！！
 7 
 8 void gb(int l,int r)
 9 {
10     if(l>=r)
11         return ;
12     int m=(l+r)/2;
13     gb(l,m); gb(m+1,r);
14     //rec
15     int i=l,j=m+1,*temp=new int[r-l+1 +1],k=1;　　//此处temp数组动态分配改为和f数组一起定义相同尺寸，用一倍的空间来去除动态内存分配的时间
16     while(i<=m&&j<=r)
17     {
18         if(f[i]<=f[j])
19             temp[k++]=f[i++];
20         else
21             temp[count+=m-i+1,k++]=f[j++];    //归并时取第二序列每个元素时第一序列中剩余元素个数即为本次该元素的逆序数
22     }
23     while(i<=m)
24         temp[k++]=f[i++];
25     while(j<=r)
26         temp[k++]=f[j++];
27     k=1;
28     while(l<=r)
29         f[l++]=temp[k++];
30     delete []temp;　　//！
31 }
32 
33 int main()
34 {
35     while(scanf("%d",&n)!=EOF)
36     {
37         int i;
38         for(i=1;i<=n;i++)
39             scanf("%d",f+i);
40         count =0;
41         gb(1,n);
42     //    for(i=1;i<=n;i++)
43     //        printf("%d ",f[i]);
44         printf("%ld
",count);    //增加int长度时记得这里对应修改l个数！！！
45     }
46     return 0;
47 }
48 
49 /***************************************************
50 User name: ***
51 Result: Accepted
52 Take time: 32ms
53 Take Memory: 1336KB
54 Submit time: 2016-12-09 19:21:49
55 ****************************************************/