Posted on 2008-09-23 18:05
Hero 阅读(520)
评论(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 for( int 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