문제요약

길이 $N$인 수열 $A$가 주어진다. 수열의 모든 원소의 값은 서로 다르며, 당신은 아래의 연산을 원하는 만큼 수행하여 수열 $A$를 오름차순으로 정렬해야 한다.

• $1 \leq i < j \leq N$인 $i$, $j$를 골라 $A_i, A_j$의 자리를 바꾸고, $X = \min(A_i, A_j)$, $Y = \max(A_i, A_j)$에 대해 기록에 정수 쌍 $(X, Y)$를 추가한다. 동일한 정수 쌍이 이미 기록되어 있다면 추가하지 않는다.

연산 과정에서 기록에 정수 쌍 $(X, Y)$를 추가할 때마다 $Y-X$의 비용이 발생한다고 할 때, 수열 $A$를 오름차순으로 정렬하면서 발생하는 비용의 합의 최솟값을 구해보자.

$(2 \leq N \leq 200\,000)$

$\left(1 \leq A_i \leq 10^9\right)$

풀이

순열 사이클 분할을 하면 각 구간에서 최대 최소만 고르는 것이 최적이라는 사실을 알 수 있다.

여기서 각 구간 사이를 연결해주기 위해 스위핑을 해주면 된다.

정답코드

from collections import deque
import sys
input = sys.stdin.readline

def bfs(s):
    visited[s] = 1
    visit = [s]
    
    q = deque()
    q.append(s)
    
    while q:
        now = q.popleft()
        
        for next in graph[now]:
            if not visited[next]:
                visited[next] = 1
                visit.append(next)
                q.append(next)
    
    return visit

n = int(input())
a = list(map(int, input().split()))
aa = sorted(a)
visited = [0]*n

d = {}
d2 = {}
for i in range(n):
    d[a[i]] = i
    d2[i] = a[i]
    
ret = []

graph = [[] for _ in range(n)]
for i in range(n):
    u = i
    v = d[aa[i]]
    graph[u].append(v)
    graph[v].append(u)

for i in range(n):
    if not visited[i]:
        ret.append(bfs(i))

arr = []
for l in ret:
    ll = []
    for i in range(len(l)):
        ll.append(d2[l[i]])
    
    ll.sort()
    arr.append((ll[0], ll[-1]))

ans = 0

arr.sort()
arr.append((int(2e9), int(2e9)))
l,r = arr[0]

for x,y in arr[1:]:
    # print(l, r, x, y)
    if r < x:
        ans += r - l
        l,r = x,y
    else:
        r = max(r, y)

print(ans)