Posted on 2008-09-23 18:45
Hero 閱讀(113)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //2299 Accepted 3732K 391MS C++ 1446B PKU
2
3 //歸并排序
4
5 #include <stdio.h>
6 #include <string.h>
7 #include <stdlib.h>
8
9 typedef long long llong ;
10 const int size = 550000 ;
11
12 int data[size] ;
13 int temp[size] ;
14
15 llong Mnum ;
16 int inn ;
17
18
19 //先定義好data[]和temp[]數組
20 void Merge( int a,int b,int c )
21 {//將data[a--b]和data[b+1--c]歸并為有序的data[a-c]
22
23 int sA = a ; //數組1的起始位置
24 int eA = b ;
25 int sB = b+1 ;//數組2的起始位置
26 int eB = c ;
27 int tt = a ; //數組3的計數器
28 while( sA<=eA && sB<=eB )
29 {
30 if( data[sA] <= data[sB] )//從小到大排序--求逆序數
31 //if( data[sA] >= data[sB] )//從大到小排序--求順序數
32 {
33 temp[tt++] = data[sA++] ;
34 }
35 else
36 {
37 temp[tt++] = data[sB++] ;
38 Mnum += (b - sA + 1) ;//求逆序數Mnum
39 }
40 }
41 while( sA <= eA ) temp[tt++] = data[sA++] ;
42 while( sB <= eB ) temp[tt++] = data[sB++] ;
43 //for( i=a; i<=c; i++ ) data[i] = temp[i] ;
44 memcpy( data+a,temp+a,(c-a+1)*sizeof(int) ) ;
45 }
46
47 void Msort( int ms,int me )
48 {//將data[ms--me]歸并排序為data[ms--me]
49 if( ms == me )
50 {
51 return ;
52 }
53 else
54 {
55 int mid = ( ms + me ) / 2 ;//一分為二
56 Msort( ms,mid ) ; //歸并左邊為有序
57 Msort( mid+1,me ) ; //歸并右邊為有序
58 Merge( ms,mid,me ) ;//兩個有序數組合并
59 }
60 }//Mnum = 0 ; Msort( 1,n ) ;
61
62 void input()
63 {
64 for( int i=1; i<=inn; i++ ) scanf( "%d", &data[i] ) ;
65 }
66
67 void process()
68 {
69 Mnum = 0 ;
70 Msort( 1, inn ) ;
71 }
72
73 void output()
74 {
75 printf( "%lld\n", Mnum ) ;
76 }
77
78 int main()
79 {
80 while( scanf( "%d", &inn ) != EOF && inn )
81 {
82 input() ;
83
84 process() ;
85
86 output() ;
87 }
88
89 return 0 ;
90 }