Posted on 2008-09-23 18:45
Hero 阅读(110)
评论(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 }