Description
Alec has a lot of eggs. One day, he want to sort them in a ascending sequence by weight. But he only can switch two eggs which are adjoining by each other because he has two hands only. Now he ask for your help, and you are enthusiastic. You decide help him calculate the total numbers of switch he need at least.
Attention: the weight of each egg less than 100,000,000 units.
Input
There are multiply test case.The first line describe the number of test case . For each test case, the first line describe the number of eggs that Alec has, . The second line describe the weight of each eggs splited by a space.
Output
Output the total number of switch that Alec need at least. One line for each test case. The total number may be very very large but fited in 64-bit integer.
Sample Input
2
2
2 1
2
2 3
Sample Output
1
0
题意：
题意：将相邻的两个元素进行排序，用到二路归并算法，
贴上代码：
1
#include <stdio.h>
2
#include <stdlib.h>
3
4
#define
MAX 100001
5
6
int
n, a[MAX], t[MAX];
7
long
long
sum;
8
9
/*
归并
*/
10
void
Merge(
int
l,
int
m,
int
r)
11
{
12
/*
p指向输出区间
*/
13
int
p =
0
;
14
/*
i、j指向2个输入区间
*/
15
int
i = l, j = m +
1
;
16
/*
2个输入区间都不为空时
*/
17
while
(i <= m && j <=
r)
18
{
19
/*
取关键字小的记录转移至输出区间
*/
20
if
(a[i] >
a[j])
21
{
22
t[p++] = a[j++
];
23
/*
a[i]后面的数字对于a[j]都是逆序的
*/
24
sum += m - i +
1
;
25
}
26
else
27
{
28
t[p++] = a[i++
];
29
}
30
}
31
/*
将非空的输入区间转移至输出区间
*/
32
while
(i <= m) t[p++] = a[i++
];
33
while
(j <= r) t[p++] = a[j++
];
34
/*
归并完成后将结果复制到原输入数组
*/
35
for
(i =
0
; i < p; i++
)
36
{
37
a[l + i] =
t[i];
38
}
39
}
40
41
/*
归并排序
*/
42
void
MergeSort(
int
l,
int
r)
43
{
44
int
m;
45
if
(l <
r)
46
{
47
/*
将长度为n的输入序列分成两个长度为n/2的子序列
*/
48
m = (l + r) /
2
;
49
/*
对两个子序列分别进行归并排序
*/
50
MergeSort(l, m);
51
MergeSort(m +
1
, r);
52
/*
将2个排好的子序列合并成最终有序序列
*/
53
Merge(l, m, r);
54
}
55
}
56
57
int
main()
58
{
59
int
i;
60
int
t;
61
scanf(
"
%d
"
, &
t);
62
while
(t--
)
63
{
64
scanf(
"
%d
"
, &
n);
65
if
(n ==
0
)
break
;
66
sum =
0
;
67
for
(i =
0
; i < n; i++
)
68
{
69
scanf(
"
%d
"
, &
a[i]);
70
}
71
MergeSort(
0
, n -
1
);
72
printf(
"
%lld\n
"
, sum);
73
}
74
return
0
;
75
}
上面代码速度没有优化，
下面的是网友的代码：
1
#include <stdio.h>
2
#define
MAX 100000
3
int
n,flag,a[MAX],b[MAX];
4
long
long
cnt;
5
void
Merge(
int
*res,
int
*cop,
int
l,
int
lt,
int
r,
int
rt)
6
{
7
int
base
=
l;
8
while
(
base
<=
rt)
9
{
10
while
((l<=lt && cop[l]<=cop[r]) || (l<=lt && r>rt)) res[
base
++]=cop[l++
];
11
while
((r<=rt && cop[l]>cop[r]) || (r<=rt && l>
lt))
12
{
13
cnt+=lt-l+
1
;
14
res[
base
++]=cop[r++
];
15
}
16
}
17
}
18
void
MergeSort()
19
{
20
int
step=
2
,semi,c,s,i,l,r,lt,rt;
21
int
*res=NULL,*cop=
NULL;
22
while
(step<
2
*
n)
23
{
24
c=n/
step;
25
s=n%
step;
26
semi=step/
2
;
27
if
(s>semi) c++
;
28
flag++
;
29
if
(flag%
2
)
30
{
31
res=
b;
32
cop=
a;
33
}
34
else
35
{
36
res=
a;
37
cop=
b;
38
}
39
for
(i=
0
;i<c;i++
)
40
{
41
l=i*
step;
42
r=l+
semi;
43
lt=r-
1
;
44
rt=(n-
1
)<(l+step-
1
)?(n-
1
):(l+step-
1
);
//
边界非整段处理
45
Merge(res,cop,l,lt,r,rt);
46
}
47
if
(rt<n-
1
){
48
for
(i=rt+
1
;i<n;i++) res[i]=cop[i];
//
非常关键，尾部剩余有序要记得拷贝
49
}
50
step*=
2
;
51
}
52
}
53
54
int
main()
55
{
56
int
i;
57
int
t;
58
scanf(
"
%d
"
, &
t);
59
while
(t--
){
60
scanf(
"
%d
"
,&
n);
61
62
flag=cnt=
0
;
63
for
(i=
0
;i<n;i++) scanf(
"
%d
"
,&
a[i]);
64
MergeSort();
65
printf(
"
%lld\n
"
,cnt);
66
67
}
68
return
0
;
69
}
另一个版本：
1
long
long
a[
100004
],b[
100004
];
int
N;
2
3
long
long
total,i,j;
4
5
void
Mergesort(
int
start,
int
end)
6
{
7
if
(start<
end){
8
int
i,j,mid=(start+end)/
2
;
9
Mergesort(start,mid);
10
Mergesort(mid+
1
,end);
11
int
t=start;j=mid+
1
;i=
start;
12
while
(i<=mid && j<=
end){
13
if
(a[i]<=
a[j])
14
b[t++]=a[i++
];
15
else
{
16
b[t++]=a[j++
];
17
total+=mid-i+
1
;
18
}
19
}
20
while
(i<=
mid)
21
b[t++]=a[i++
];
22
while
(j<=
end)
23
b[t++]=a[j++
];
24
for
(i=start;i<=end;i++
)
25
a[i]=
b[i];
26
}
27
}
28
29
30
int
main()
31
{
32
int
t;
33
double
ac;
34
scanf(
"
%d
"
, &
t);
35
while
(t--
) {
36
scanf(
"
%d
"
,&
N);
37
total=
0
;
38
for
(i=
0
;i<N;i++
)
39
scanf(
"
%lld
"
,&
a[i]);
40
Mergesort(
0
,N-
1
);
41
ac = (total+N)/(N*
1.0
);
42
printf(
"
%.2f\n
"
,ac);
43
44
}
45
}
