我希望你是我独家记忆

一段永远封存的记忆,随风而去
posts - 263, comments - 31, trackbacks - 0, articles - 3
   :: 首页 :: 新随笔 ::  :: 聚合  :: 管理

归并求逆序数

Posted on 2008-09-23 18:05 Hero 阅读(469) 评论(2)  编辑 收藏 引用 所属分类: 代码如诗--ACM
 1 //5086 Accepted C++ 0.2460 s 1036 k Hero 
 2 
 3 #include <stdio.h>
 4 #include <string.h>
 5 #include <stdlib.h>
 6 
 7 const int size = 101000 ;
 8 typedef long long llong ;
 9 
10 llong Mnum ;
11 
12 int data[size] ;
13 int temp[size] ;
14 
15 int innum ;
16 int inn, inm ;
17 
18 //先定义好data[]和temp[]数组
19 void Merge( int a,int b,int c ) 
20 {//将data[a--b]和data[b+1--c]归并为有序的data[a-c]
21 
22     int sA = a ;  //数组1的起始位置
23     int eA = b ;
24     int sB = b+1 ;//数组2的起始位置
25     int eB = c ;
26     int    tt = a ;  //数组3的计数器
27     while( sA<=eA && sB<=eB )
28     {
29         //if( data[sA] <= data[sB] )//从小到大排序
30         if( data[sA] >= data[sB] )//从大到小排序
31         {
32             temp[tt++= data[sA++] ;
33         }
34         else
35         {
36             temp[tt++= data[sB++] ;
37             Mnum += (b - sA + 1) ;//求逆序数Mnum
38         }
39     }
40     while( sA <= eA ) temp[tt++= data[sA++] ;
41     while( sB <= eB ) temp[tt++= data[sB++] ;
42     //for( i=a; i<=c; i++ )    data[i] = temp[i] ;
43     memcpy( data+a,temp+a,(c-a+1)*sizeof(int) ) ;
44 }
45 
46 void Msort( int ms,int me )
47 {//将data[ms--me]归并排序为data[ms--me]
48     if( ms == me )
49     {
50         return ;
51     }
52     else
53     {
54         int mid = ( ms + me ) / 2 ;//一分为二
55         Msort( ms,mid ) ;    //归并左边为有序
56         Msort( mid+1,me ) ;  //归并右边为有序
57         Merge( ms,mid,me ) ;//两个有序数组合并
58     }
59 }//Mnum = 0 ; Msort( 1,n ) ;
60 
61 void input()
62 {
63     scanf( "%d %d"&inn, &inm ) ;
64     int inx ; data[0= 0 ;
65     forint i=1; i<=inn; i++ )
66     {
67         scanf( "%d"&inx ) ; inx = inx - inm ;
68         data[i] = data[i-1+ inx ;
69     }
70 }
71 
72 void process()
73 {
74     Mnum = 0 ;
75     Msort( 0, inn ) ;
76 }
77 
78 void output()
79 {
80     printf( "%lld\n", Mnum ) ;
81 }
82 
83 int main()
84 {
85     while( scanf( "%d"&innum ) != EOF )
86     {
87         while( innum -- )
88         {
89             input() ;
90 
91             process() ;
92 
93             output() ;
94         }
95     }
96 
97     return 0 ;
98 }
99 

Feedback

# re: 归并求逆序数  回复  更多评论   

2012-10-13 22:59 by 王玉
Mnum += (b - sA + 1) ;//求逆序数Mnum 这句话对么 怎么感觉怪怪的 求指教

# re: 归并求逆序数  回复  更多评论   

2012-10-13 23:02 by 王玉
Mnum += eB - sB + 1 而且放在if( data[sA] >= data[sB] )这个判断里面??

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