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
題意：
題意：將相鄰的兩個元素進(jìn)行排序，用到二路歸并算法，
貼上代碼：
?
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指向輸出區(qū)間
*/
13
int
p =
0
;
14
/*
i、j指向2個輸入?yún)^(qū)間
*/
15
int
i = l, j = m +
1
;
16
/*
2個輸入?yún)^(qū)間都不為空時
*/
17
while
(i <= m && j <=
r)
18
{
19
/*
取關(guān)鍵字小的記錄轉(zhuǎn)移至輸出區(qū)間
*/
20
if
(a[i] >
a[j])
21
{
22
t[p++] = a[j++
];
23
/*
a[i]后面的數(shù)字對于a[j]都是逆序的
*/
24
sum += m - i +
1
;
25
}
26
else
27
{
28
t[p++] = a[i++
];
29
}
30
}
31
/*
將非空的輸入?yún)^(qū)間轉(zhuǎn)移至輸出區(qū)間
*/
32
while
(i <= m) t[p++] = a[i++
];
33
while
(j <= r) t[p++] = a[j++
];
34
/*
歸并完成后將結(jié)果復(fù)制到原輸入數(shù)組
*/
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
/*
對兩個子序列分別進(jìn)行歸并排序
*/
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
}
?
?
上面代碼速度沒有優(yōu)化，
下面的是網(wǎng)友的代碼：
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];
//
非常關(guān)鍵，尾部剩余有序要記得拷貝
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
}
?
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
