ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 1851 |
문제명 | 추 정렬하기 |
레벨 | 다이아몬드 5 |
분류 |
그리디 |
시간복잡도 | O(n) |
인풋사이즈 | n<=100,000 |
사용한 언어 | Python |
제출기록 | 30864KB / 76ms |
최고기록 | 76ms |
해결날짜 | 2022/02/28 |
"""Solution code for "BOJ 1851. 추 정렬하기".
- Problem link: https://www.acmicpc.net/problem/1851
- Solution link: http://www.teferi.net/ps/problems/boj/1851
Tags: [Greedy]
"""
import sys
def main():
n = int(sys.stdin.readline())
w = [int(sys.stdin.readline()) for x in range(n)]
min_w = min(w)
orders = sorted(range(n), key=w.__getitem__)
is_visited = [False] * n
answer = 0
for i in range(n):
if is_visited[i]:
continue
weights = []
cur = i
while not is_visited[cur]:
is_visited[cur] = True
weights.append(w[cur])
cur = orders[cur]
answer += min(
sum(weights) + min(weights) * (len(weights) - 2),
sum(weights) + min(weights) + min_w * (len(weights) + 1))
print(answer)
if __name__ == '__main__':
main()