gzwzm06

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
 1 #include <stdio.h>
 2 
 3 const int MAXN = 500001 ;
 4 __int64 a[MAXN] , c[MAXN] , cnt ;
 5 
 6 void Merge( int le, int mid, int rh);
 7 
 8 void MergeSort(int le, int rh){
 9 
10     
11     if (rh>le)
12     {
13         int mid = (le+rh) >> 1;
14         MergeSort(le,mid);
15         MergeSort(mid + 1,rh);
16         Merge(le, mid, rh);
17     }
18 }
19 
20 void Merge(int le, int mid, int rh)
21 {
22         int i, j,
23         tmp = 1;
24         for (i = le, j = mid+1; i <= mid && j <= rh; ) 
25         {
26             if (a[j] < a[i])
27             {
28                 c[tmp++= a[j++];
29                 cnt += mid - i + 1;    //记录逆序数    
30             }
31             else   c[tmp++= a[i++];
32         }
33        while ( j <= rh )
34                 c[tmp++= a[j++];
35        while( i <= mid )  
36                 c[tmp++= a[i++];
37 
38         for (i = le; i <= rh; ++i)
39         {
40             a[i] = c[i - le + 1];
41         }
42         
43 }  
44 
45 
46 int main()
47 {
48     int n , i ;
49 
50     while ( scanf("%d"&n) && n != 0 )
51     {
52         for ( i = 0 ; i < n ; i++ )
53         {
54             scanf("%I64d"&a[i]) ;
55         }
56         cnt = 0 ;
57         MergeSort( 0, n - 1 ) ;
58 
59         printf("%I64d\n", cnt) ;
60     }
61     return 0 ;
62 }

posted on 2008-11-13 00:37 阅读(396) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理