백준
백준 1517번: 버블 소트
2호0
2023. 2. 9. 20:59
https://www.acmicpc.net/problem/1517
1517번: 버블 소트
첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다.
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
import sys
input = sys.stdin.readline
result = 0
def merge_sort(s,e):
global result
if e-s < 1:
return
m = int(s+(e-s)/2)
merge_sort(s,m)
merge_sort(m+1,e)
for i in range(s,e+1):
tmp[i] = a[i]
k=s
index1 = s
index2 = m+1
while index1<=m and index2 <=e:
if tmp[index1]>tmp[index2]:
a[k] = tmp[index2]
result = result+index2-k
k+=1
index2+=1
else:
a[k] = tmp[index1]
k+=1
index1 +=1
while index1 <=m:
a[k] = tmp[index1]
k+=1
index1+=1
while index2 <=e:
a[k] = tmp[index2]
k+=1
index2+=1
n = int(input())
a = list(map(int, input().split()))
a.insert(0,0)
tmp = [0]*(n+1)
merge_sort(1,n)
print(result)
|
cs |