Ultra-QuickSort--POJ 2299
30769 단어 Quicksort
2. 주의사항: 트리 수조의 업데이트, 병합 정렬의 귀속;긴 정형으로 결과를 저장하십시오.
3, 구현 방법: (트리 배열: Memory: 11016K, Time: 797MS)
1
#include
<
iostream
>
2
#include
<
algorithm
>
3
using
namespace
std;
4
5
struct
Node{
6
int
id;
7
__int64 value;
8
};
9
10
int
n,tree[
500010
],array[
500010
];
11
__int64 cnt;
12
Node No[
500010
];
13
14
int
cmp(Node N1,Node N2)
15
{
16
return
N1.value
<
N2.value;
17
}
18
19
//
20
void
Getarray()
21
{
22
for
(
int
i
=
1
;i
<=
n;i
++
)
23
array[No[i].id]
=
i;
24
}
25
26
void
Init()
27
{
28
cnt
=
0
;
29
for
(
int
i
=
1
;i
<=
n;i
++
)
30
{
31
scanf(
"
%I64d
"
,
&
No[i].value);
32
No[i].id
=
i;
33
}
34
sort(No
+
1
,No
+
n
+
1
,cmp);
35
Getarray();
36
memset(tree,
0
,
sizeof
(tree));
37
}
38
39
void
Update(
int
id,
int
value)
40
{
41
while
(id
<=
n)
42
{
43
tree[id]
+=
value;
44
id
+=
(id
&
-
id);
45
}
46
}
47
48
__int64 Getsum(
int
id)
49
{
50
__int64 sum
=
0
;
51
while
(id
>
0
)
52
{
53
sum
+=
tree[id];
54
id
-=
(id
&
-
id);
55
}
56
return
sum;
57
}
58
59
int
main()
60
{
61
while
(cin
>>
n
&&
n)
62
{
63
Init();
64
for
(
int
i
=
1
;i
<=
n;i
++
)
65
{
66
Update(array[i],
1
);
67
cnt
+=
i
-
Getsum(array[i]);
68
}
69
printf(
"
%I64d
"
,cnt);
70
}
71
return
0
;
72
}
4, 구현 방법: (Mergesort: Memory: 3692K, Time: 391MS)
1
#include
<
iostream
>
2
#include
<
algorithm
>
3
using
namespace
std;
4
5
__int64 sum;
6
int
a[
500000
],b[
500000
];
7
8
//
9
void
guibin(
int
begin,
int
mid,
int
end)
10
{
11
int
i,j,p
=
0
;
12
for
(i
=
begin,j
=
mid
+
1
;i
<=
mid
&&
j
<=
end;)
13
{
14
if
(a[i]
>
a[j])
15
{
16
sum
+=
(mid
-
i
+
1
);
17
b[p
++
]
=
a[j
++
];
18
}
19
else
20
b[p
++
]
=
a[i
++
];
21
}
22
while
(i
<=
mid)
23
b[p
++
]
=
a[i
++
];
24
while
(j
<=
end)
25
b[p
++
]
=
a[j
++
];
26
for
(i
=
0
;i
<
p;i
++
)
27
a[i
+
begin]
=
b[i];
28
}
29
30
//
31
void
paixu(
int
begin,
int
end)
32
{
33
if
(begin
<
end)
34
{
35
int
mid
=
(begin
+
end)
/
2
;
36
paixu(begin,mid);
37
paixu(mid
+
1
,end);
38
guibin(begin,mid,end);
39
}
40
}
41
42
int
main()
43
{
44
int
num;
45
while
(
1
)
46
{
47
sum
=
0
;
48
scanf(
"
%d
"
,
&
num);
49
if
(num
==
0
)
50
break
;
51
int
i;
52
for
(i
=
0
;i
<
num;i
++
)
53
scanf(
"
%d
"
,
&
a[i]);
54
paixu(
0
,num
-
1
);
55
printf(
"
%I64u
"
,sum);
56
}
57
return
1
;
58
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Quicksort 하나로 얼마나 짧게 쓸 수 있는지.Step 2: 수조의 어떤 원소를 얻을 수 있습니다. Step4: 이전에 한 절차가 수조를 나누는 과정이라는 것을 쉽게 발견할 수 있으며 이해하기 쉽도록 함수로 끌어올릴 수 있다.이와 동시에 빠른 속도로 좌우 두 부...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
