Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Minimum Cost Sort

  You are given $n$ integers $w_i (i = 0, 1, ..., n-1)$ to be sorted in ascending order. You can swap two integers $w_i$ and $w_j$. Each swap operation has a cost, which is the sum of the two integers $w_i + w_j$. You can perform the operations any number of times.

  Write a program which reports the minimal total cost to sort the given integers.

Input

  In the first line, an integer $n$ is given. In the second line, $n$ integers $w_i (i = 0, 1, 2, ... n-1)$ separated by space characters are given.

Output

  Print the minimal cost in a line.

Constraints

$1 \leq n \leq 1,000$

$0 \leq w_i\leq 10^4$

$w_i$ are all different

Sample Input 1

5
1 5 3 4 2

Sample Output 1

7

Sample Input 2

4
4 3 2 1

Sample Output 2

10



Sample input:
5
1 5 3 4 2


Sample output:
7

Submission status: Accepted

Solution code:
def minimum_cost(A, m, k):
    """整数列 A を最小コストソートでソートした場合の総コストを返す。

    A 内の整数は 0 <= <= k のすべて異なる整数であり、
    m がその中で最小の数。
    """
    # A 内の整数 i の出現数を C[i] に記録していく。
    C = [0 for _ in range(0, k + 1)]
    for x in A:
        C[x] += 1
    
    # A 内の i 番目の整数のソート後の位置（0 起点）を C[i] に記録する。
    C[0] -= 1
    for i in range(1, k + 1):
        C[i] += C[i - 1]

    total_cost = 0
    n = len(A)
    for i in range(n):
        j = i
        length = 0
        sum_weight = 0
        cur_min = k + 1
        while C[A[j]] >= 0:
            length += 1
            sum_weight += A[j]
            if A[j] < cur_min:
                cur_min = A[j]
            z = C[A[j]]
            C[A[j]] = -1
            j = z
        if length >= 3:
            if cur_min > m:
                total_cost += min(sum_weight + cur_min * (length - 2),
                                  (sum_weight - cur_min) + m * (length - 1) + 2 * (m + cur_min))
            else:
                total_cost += sum_weight + cur_min * (length - 2)
        elif length == 2:
            total_cost += sum_weight

    return total_cost

if __name__ == '__main__':
    import sys

    n = int(input())
    A = list(map(int, sys.stdin.readline().split()))
    print(minimum_cost(A, min(A), max(A)))

Submission status: Accepted

Solution code:
def min_cost(nums, n):
    sorted_list = sorted(nums)
    global_min = sorted_list[0]
    check_list = [False] * n
    cost = 0
    for start_idx in range(n):
        if check_list[start_idx]:
            pass
        else:
            start_num = nums[start_idx]
            cycle_idx = start_idx
            cycle_count = 0
            min_num = start_num
            w_sum = 0
            while True:
                check_list[cycle_idx] = True
                cycle_num = nums[cycle_idx]
                w_sum += cycle_num
                next_idx = sorted_list.index(cycle_num)
                min_num = min(min_num, cycle_num)
                if next_idx == start_idx:
                    break
                cycle_idx = next_idx
                cycle_count += 1
            if cycle_count >= 1:
                cost1 = w_sum + (cycle_count - 1) * min_num
                cost2 = w_sum + min_num + (cycle_count + 2) * global_min
                cost += min(cost1, cost2)
    return cost


def main():
    n = int(input())
    nums = list(map(int, input().split(" ")))
    cost = min_cost(nums, n)
    print(cost)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy

def solve():
    ans = 0
    V = [False] * n
    B = sorted(A)
    maxWeight = B[-1]
    minWeight = B[0]
    T = [None] * (maxWeight + 1)
    for i in range(n):
        T[B[i]] = i
        
    for i in range(n):
        if V[i]:
            continue
        
        cur = i
        S = 0
        m = maxWeight
        an = 0
        while True:
            V[cur] = True
            an += 1
            v = A[cur]
            m = min(m, v)
            S += v
            cur = T[v]
            if V[cur]:
                break
        ans += min(S + (an - 2) * m, m + S + (an + 1) * minWeight)
    
    return ans

n = int(input())
A = list(map(int, input().split()))

ans = solve()
print(ans)

Submission status: Accepted

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def update(j, min_w, sum_w, wn):
        j = ia[j][0]
        fin[j] = True
        w = ia[j][1]
        if w < min_w: min_w = w
        return j, min_w, sum_w + w, wn + 1

    inf = 10 ** 16
    n = int(input())
    aa = list(map(int, input().split()))
    ia = [[i, a] for i, a in enumerate(aa)]
    ia.sort(key=lambda x: x[1])
    #print(ia)
    fin = [False] * n
    min_a = ia[0][1]
    ans = 0
    for i in range(n):
        if fin[i]: continue
        min_w = inf
        sum_w = 0
        wn = 0

        j, min_w, sum_w, wn = update(i, min_w, sum_w, wn)
        if i == j: continue

        while j != i:
            j, min_w, sum_w, wn = update(j, min_w, sum_w, wn)

        ans += min(sum_w + min_w * (wn - 2), sum_w + min_a * (wn + 1) + min_w)
    print(ans)

main()

Submission status: Accepted

Solution code:
import copy
MAX_LENGTH = 1000
MAX_WEIGHT = 10001


def minimum_sort_cost(A):
    cost = 0
    n = len(A)
    s = min(A)
    B = sorted(A)
    V = [False] * n
    T = [None] * MAX_WEIGHT

    for i in range(n):
        T[B[i]] = i
    
    for i in range(n):
        if V[i]:
            continue

        cur = i
        circle_len = 0
        min_weight = MAX_WEIGHT
        circle_weight = 0

        while(True):
            V[cur] = True
            circle_len += 1
            weight = A[cur]
            min_weight = min(min_weight, weight)
            circle_weight += weight
            cur = T[weight]

            if V[cur]:
                break
        
        cost += min(circle_weight + (circle_len - 2) * min_weight,\
             min_weight + circle_weight + (circle_len + 1) * s)
    
    return cost


if __name__ == "__main__":
    n = int(input())
    *A, = map(int, input().split())
    print(minimum_sort_cost(A))

Submission status: Accepted

Solution code:

def solve(A, N):
    answer = 0

    B = list(A)
    V = [False] * N
    T = [None] * 10001
    s = min(A)

    B.sort()

    # print(A)
    # print(B)

    for i in range(N):
        T[B[i]] = i

    for i in range(N):
        if V[i] is True:  # すでにカーソルが来ていたら飛ばす。
            continue

        cur = i  # カーソル
        S = 0
        m = 10000  # VMAX
        an = 0  # サイクルの長さ

        while True:
            V[cur] = True  # まずは今の位置を走査済みにする。
            an += 1  # サイクルの長さを増やす
            v = A[cur]  # 入力列の値
            m = min(m, v)  # このサイクルの最小値
            S += v  # 今の値の重さを足す。SはΣwi
            cur = T[v]  # 次のカーソルの位置を決める
            if V[cur]:  # 次のカーソルの位置がTrueなら
                break  # サイクルの始まりまで戻ってきたということ。

        # この状態で、
        # an = サイクルの長さ
        # S = wiの合計の重さ
        # m = このサイクルの最小値
        # の3つが分かっている。

        answer += min(S + (an - 2) * m, m + S + (an + 1) * s)

    return answer


N = int(input())
A = list(map(int, input().split()))

answer = solve(A, N)
print(answer)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
b=sorted(a)
c=0
for i in range(n-1):
    t,cnt=0,0
    x=a.index(b[i])
    while x!=i:
        y=a.index(b[x])
        a[x],a[y]=b[x],b[i]
        t+=b[x]+b[i]
        cnt+=1
        x=y
    if cnt:
        c+=min(t,(b[i]+b[0])*2+t-(b[i]-b[0])*cnt)
print(c)

Submission status: Accepted

Solution code:
n = int(input())
W = list(map(int,input().split()))
W_2 = W[:]
sorted_W = sorted(W)
cost = 0
for i in range(n):
    if i==0:
        while W[i]!=sorted_W[i]:
            a=W.index(sorted_W[i])
            b=W.index(sorted_W[a])
            W[a],W[b]=W[b],W[a]
            W_2[a],W_2[b]=W_2[b],W_2[a]
            cost+=W[a]+W[b]
    else:
        cost1=0
        cost2=0
        while W[i]!=sorted_W[i]:
            a=W.index(sorted_W[i])
            b=W.index(sorted_W[a])
            W[a],W[b]=W[b],W[a]
            cost1+=W[a]+W[b]
        c = W_2.index(sorted_W[i])
        W_2[0],W_2[c]=W_2[c],W_2[0]
        cost2+=W_2[0]+W_2[c]
        while W_2[0]!=sorted_W[0]:
            a=W_2.index(sorted_W[0])
            b=W_2.index(sorted_W[a])
            W_2[a],W_2[b]=W_2[b],W_2[a]
            cost2+=W_2[a]+W_2[b]
        if cost1<=cost2:
            W_2=W[:]
            cost+=cost1
        else:
            W=W_2[:]
            cost+=cost2
print(cost)

Submission status: Accepted

Solution code:
n = int(input())
w = list(map(int, input().split()))
b = w[:]
w.sort()
s = w[0]

class Solve():
    def __init__(self, w, b, s):
        self.w = w
        self.b = b
        self.s = s
        self.ans = 0
        self.v = [0] * n
    
    def sort(self):
        T = [0] * 10001
        for i in range(n):
            T[self.w[i]] = i
        for i in range(n):
            if self.v[i]:
                continue
            cur = i
            S = 0
            m = 10001
            an = 0
            while 1:
                self.v[cur] = 1
                an += 1
                l = self.b[cur]
                m = min(m, l)
                S += l
                cur = T[l]
                if self.v[cur]:
                    break
            self.ans += min(S + (an - 2) * m, S + m +(an + 1) * self.s)
        return self

cost = Solve(w, b, s).sort()
print(cost.ans)

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/6/ALDS1_6_D
# 本の解説がわかりやすい
# ここでは本には書いてないことの補足を意識しながらコメントを付けていく
WMAX = 10**4 + 1
n = int(input())
A = list(map(int, input().split()))
B = sorted(A)
is_visited = [False] * n  # 巡回管理用
next_idxs = {}  # Aの要素について、これのkeyを見れば、その数字がsort後にどの位置にあるのかわかるように対応させる
for i, b in enumerate(B):
    next_idxs[b] = i

m_A = min(A)  # globalで一番小さい要素

# ソート後の並び順から巡回可能なグループから答えを計算する
# グループ内の最小の要素をm, グループの和をS, グループ内の要素数をn2とする。
# 具体的には,m*(n2-2) + S もしくは m + S + (1+n2)*m_Aのうち小さい方
ans = 0
for i in range(n):
    if is_visited[i]:
        continue  # 巡回済みならば次へ
    cur = i  # 巡回制御用のidx #探索済みでないiが入るはず
    S = 0  # 合計管理用
    n2 = 0
    m = WMAX  # グループ内の最小値探索用
    while True:
        # まずはもろもろの値を更新
        is_visited[cur] = True
        S += A[cur]
        m = min(m, A[cur])
        n2 += 1
        # ここで次のidxを取得する
        cur = next_idxs[A[cur]]
        if is_visited[cur]:
            break  # もし一周したらおわり
    # ループ内で完結したほうがいいのか外から要素を変えいてきたほうがいいのか
    # 小さい方を採用して答えに足し込む
    ans += min(m*(n2-2)+S, m+S+(1+n2)*m_A)

print(ans)

Submission status: Accepted

Solution code:
VMAX = 10000

def minCostSort(A, n):
	global VMAX
	VMIN = min(A)
	ans = 0
	B = A.copy()
	B.sort()
	T = [0] * (VMAX + 1)
	for i in range(n):
		T[B[i]] = i
	V = [False] * n
	for i in range(n):
		if V[i]:
			pass
		else:
			index = i
			minv = VMAX
			count = 0
			cycleweight = 0
			while 1:
				V[index] = True
				count += 1
				value = A[index]
				minv = min(minv, value)
				cycleweight += value
				index = T[value]
				if V[index]:
					break
			ans += min(cycleweight + (count - 2) * minv, cycleweight + minv + (count + 1) * VMIN)
	return ans


if __name__ == "__main__":
	n = int(input())
	A = list(map(int, input().split()))
	print(minCostSort(A, n))

Submission status: Accepted

Solution code:
def solve(n, A):
    def cycles():
        V = [False] * n
        B = sorted(A)
        T = {B[i]: i for i in range(n)}
        C = []

        for i in range(n):
            if V[i]:
                continue
            cur = i
            cycle = []
            while not V[cur]:
                V[cur] = True
                cycle.append(cur)
                cur = T[A[cur]]
            C.append(cycle)

        return C

    ans = 0
    s = min(A)

    for cycle in cycles():
        S = sum([A[i] for i in cycle])
        m = min([A[i] for i in cycle])
        an = len(cycle)
        ans += min(S + (an - 2) * m, m + S + (an + 1) * s)

    return ans


def main():
    n = int(input())
    A = [int(x) for x in input().split()]

    print(solve(n, A))


main()

Submission status: Accepted

Solution code:
n = int(input())
W = list(map(int, input().split()))

W_org = W[:]
W_org_idx = {w:i for i, w in enumerate(W_org)}
W_srt = list(sorted(W[:]))
W_srt_idx = {w:i for i, w in enumerate(W_srt)}

#print(W_org)
#print(W_org_idx)
#print(W_srt)
#print(W_srt_idx)


def rec(idx, ret):
    if W_org[idx] in ret:
        return ret
    
    ret.append(W_org[idx])
    idx = W_srt_idx[W_org[idx]]
    return rec(idx, ret)

ans = 0
searched = set()
all_min_r = min(W_org)
for i in range(n):    
    if W_org[i] in searched:
        continue
    ret = rec(i, [])
    for r in ret:
        searched.add(r)
    
    if len(ret) == 1:
        continue
    elif len(ret) == 2:
        ans += sum(ret)
    else:
        #print(ret)
        min_r = min(ret)
        ans_a = sum(ret) + len(ret)*min_r - 2*min_r
        
        ans_b = 2*(all_min_r+min_r) + (sum(ret)-min_r+all_min_r) + len(ret)*all_min_r - 2*all_min_r
        ans += min(ans_a, ans_b)

print(ans)

Submission status: Accepted

Solution code:
#最小コストソート
n = int(input())
A = list(map(int, input().split()))
#整列
B = sorted(A)
#サイクルに採用されたか否か
C = [0 for _ in range(n)]
CNT = 0
minA = B[0]

for i in range(n):
    #正しい位置にいるか
    if A[i] == B[i]:
        C[i] == 1
    #サイクルに採用済みか
    elif C[i] == 0:
        cyc = []
        ind = i
        #サイクル作成
        while C[ind] == 0:
            a = A[ind]
            cyc.append(a)
            C[ind] = 1
            ind = B.index(a)
        #2種のコスト計算
        mincyc = min(cyc)
        cost1 = sum(cyc) + (len(cyc) - 2) * mincyc
        cost2 = sum(cyc) + mincyc + (len(cyc) + 1) * minA
        if cost1 > cost2:
            CNT += cost2
        else:
            CNT += cost1
    else:
        pass
print(CNT)

Submission status: Accepted

Solution code:
MAX = 1000
VMAX = 10000


def main():
    n = int(input())
    
    a_s = list(map(int, input().split(' ')))
    minimum = min(a_s)

    ans = 0

    t_s = [0] * (VMAX+1)
    b_s = [a for a in a_s]
    v_s = [False for _ in range(n)]
    b_s = sorted(b_s)

    for i in range(n):
        t_s[b_s[i]] = i

    for i in range(n):
        if v_s[i]:
            continue
        cur = i
        S = 0
        m = VMAX
        a_n = 0

        while True:
            v_s[cur] = True
            a_n += 1
            v = a_s[cur]
            m = min(m, v)
            S += v
            cur = t_s[v]
            if v_s[cur]:
                break
        ans += min(S + (a_n-2)*m, m+S+(a_n+1)*minimum)
    
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def calc_loop_cost(loop, min_w):
    if len(loop) == 1:
        return 0
    elif len(loop) == 2:
        return loop[0] + loop[1]
    else:
        cost1 = sum(loop) + (len(loop) - 2) * min(loop)
        cost2 = sum(loop) + min(loop) + (len(loop) + 1) * min_w
        return min(cost1, cost2)

n = int(input())
org_list = [int(s) for s in input().split()]
sorted_list = sorted(org_list)
check_list = [False] * n
loop_list = []
for i in range(n):
    if check_list[i]:
        continue

    loop = []
    check_list[i] = True
    loop.append(org_list[i])
    next_idx = sorted_list.index(org_list[i])
    while next_idx != i:
        check_list[next_idx] = True
        loop.append(org_list[next_idx])
        next_idx = sorted_list.index(org_list[next_idx])

    loop_list.append(loop)

min_w = sorted_list[0]
cost_sum = 0
for lp in loop_list:
    cost_sum += calc_loop_cost(lp, min_w)

print(cost_sum)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))

B = sorted(A)
c = 0

for i in range(n-1):
    t = cnt = 0
    x = A.index(B[i])
    
    while x != i:
        y = A.index(B[x])
        A[x], A[y] = B[x], B[i]
        cnt += 1
        t += B[x] + B[i]
        x = y
    if cnt:
        c += min(t, (B[i]+B[0])*2+t-(B[i]-B[0])*cnt)
print(c)

Submission status: Accepted

Solution code:
n = int(input())
wlist = list(map(int,input().split()))
wdic = {j:i for i,j in enumerate(wlist)}
wlist.sort()
cost = 0
used = [0]*n
res = []
for i in range(n):
    storage = []
    if used[i]:
        continue # next loop
    w = wlist[i]
    minimum = w
    used[i] = 1
    a = wdic[w]
    b = wlist[a]
    storage.append(w)
    while b not in storage:
        w = b
        used[a] = 1
        a = wdic[w]
        b = wlist[a]
        storage.append(w)
        #print(w,a,b,storage)
    ls = len(storage)
    cost += (sum(storage) - minimum)
    res.append((minimum,ls))
m,l = res[0]
if l>=2:
    cost += m*(l-1)
for minimum,ls in res[1:]:
    if ls>=2:
        cost += min(2*(m+minimum)+m*(ls-1), minimum*(ls-1))
    
print(cost)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n = int(input())
    elements = list(map(lambda x: int(x), input().split()))
    sorted_elements = sorted(elements)
    total_cost = 0

    for i in range(n - 1):
        cost = 0
        cnt = 0
        x_idx = elements.index(sorted_elements[i])
        while i != x_idx:
            y_idx = elements.index(sorted_elements[x_idx])
            elements[x_idx], elements[y_idx] = (sorted_elements[x_idx],
                                                sorted_elements[i])
            cnt += 1
            cost += sorted_elements[x_idx] + sorted_elements[i]
            x_idx = y_idx
        if cnt:
            total_cost += min(cost,
                              (sorted_elements[i] + sorted_elements[0]) * 2 + cost
                              - (sorted_elements[i] - sorted_elements[0]) * cnt)

    print(total_cost)

Submission status: Accepted

Solution code:
MAXV = 10**4

if __name__ == '__main__':
    n = int(raw_input())
    # input, range[1, n], according to counting sort
    A = [0] + map(int, raw_input().split())
    # counter, range: [0, k]
    # so why use counting sort?
    # because it's easy to find where an element go after sorting
    C = [0 for i in range(MAXV + 1)]
    min_of_all = MAXV + 1

    for i in range(1, n + 1):
        C[A[i]] += 1
        min_of_all = min(min_of_all, A[i])

    for i in range(1, MAXV + 1):
        C[i] += C[i - 1]

    # find all cycles of moves
    # if V[i] is 1, then A[i] is already covered in some cycle
    V = [0 for i in range(n + 1)]
    total_cost = 0
    for i in range(1, n + 1):
        if V[i] == 1:
            continue
        V[i] = 1  # mark as visited
        size_of_cycle = 1  # the number of elements in the cycle
        min_of_cycle = A[i]
        sum_of_cycle = A[i]
        j = i  # iterator
        while True:
            j = C[A[j]]
            if i == j:
                break
            V[j] = 1
            size_of_cycle += 1
            sum_of_cycle += A[j]
            min_of_cycle = min(min_of_cycle, A[j])
        if size_of_cycle == 1:
            # only one element, no move, cost is zero
            continue

        cost = sum_of_cycle + (size_of_cycle - 2) * min_of_cycle
        if min_of_all < min_of_cycle:
            # swap back and forth, positive
            diff = 2 * (min_of_all + min_of_cycle)
            # diff in the sum of the cycle, negative
            diff += min_of_all - min_of_cycle
            # diff in (n-2)*min(w), negative
            diff += (size_of_cycle - 2) * (min_of_all - min_of_cycle)
            if diff < 0:
                cost += diff
        total_cost += cost

    print total_cost

Submission status: Accepted

Solution code:
# INPUT
n = int(input())
W = list(map(int, input().split()))


# PROCESS
cost = 0
W_sorted = sorted(W)
W_min = W_sorted[0]

for i in range(n - 1):
    cycle_min = W_sorted[i]
    cost_cycle_in = 0
    cnt_change = 0

    index_cycle_min = W.index(cycle_min)

    while index_cycle_min != i:
        cycle_change = W_sorted[index_cycle_min]
        index_cycle_change = W.index(cycle_change)

        W[index_cycle_min], W[index_cycle_change] = cycle_change, cycle_min
        cost_cycle_in += cycle_min + cycle_change

        cnt_change += 1
        index_cycle_min = index_cycle_change

    if cnt_change:
        cost_cycle_out = (
            cost_cycle_in
          + (cycle_min + W_min) * 2
          - (cycle_min - W_min) * cnt_change
        )

        cost += min(cost_cycle_in, cost_cycle_out)


# OUTPUT
print(cost)

Submission status: Accepted

Solution code:
n = int(input())
W = [[int(i)] for i in input().split()]
for ni in range(n):
    W[ni].append(ni)
W.sort()
G = [[] for i in range(n)]
i = 0
j = 0
cnt = 0
D = []
while cnt < n:
    if W[i][0] in G[j]:
        j += 1
        while i in D:
            i += 1
    else:
        G[j].append(W[i][0])
        D.append(i)
        cnt += 1
        i = W[i][1]
group_num = j + 1
cost = 0
W_min = min([min(G[i]) for i in range(group_num)])
for gi in range(group_num):
    if len(G[gi]) > 1:
        if (min(G[gi])+W_min)*2 > (min(G[gi])-W_min)*(len(G[gi])-1):
            cost += sum(G[gi])+ (len(G[gi])-2)*min(G[gi])
        else:
            cost += sum(G[gi])-min(G[gi])+ (len(G[gi])-1)*W_min+(min(G[gi])+W_min)*2

print(cost)

Submission status: Accepted

Solution code:
def solve(A):
    correct_a = sorted(A)
    correct_index = {n: i for i, n in enumerate(correct_a)}
    ans, min_n = 0, correct_a[0]
    cycles = []
    used = [0]*len(A)
    for i in filter(lambda i: not used[i], range(len(A))):
        used[i] = 1
        cycle, next_i = [i], correct_index[A[i]]
        while next_i != i:
            cycle.append(next_i)
            used[next_i] = 1
            next_i = correct_index[A[next_i]]
        cycles.append(cycle)

    for cycle in cycles:
        if len(cycle) == 2:
            ans += correct_a[cycle[0]] + correct_a[cycle[1]]
        elif len(cycle) > 2:
            ans += (min(correct_a[cycle[0]]*(len(cycle)-1), correct_a[cycle[0]]*2 + min_n*(len(cycle)+1))
                    + sum(correct_a[i] for i in cycle[1:]))

    return ans


if __name__ == "__main__":
    input()
    a = list(map(int, input().split()))
    print(solve(a))

Submission status: Accepted

Solution code:
def minimumCostSort(arr, arr_size):
    cost = 0
    sortarr = sorted(arr)
    cyclecontainer = []
    for i in range(arr_size):
        cycle = [arr[i]]
        next = sortarr.index(arr[i])
        while arr[next] != arr[i]:
            cycle += [arr[next]]
            next = sortarr.index(arr[next])
        cycle = sorted(cycle)
        if cycle not in cyclecontainer:
            cyclecontainer.append(cycle)
            if len(cycle) == 1:
                pass
            elif len(cycle) == 2:
                cost += sum(cycle)
            elif len(cycle) >= 3:
                cost += min(sum(cycle)+((len(cycle)-2)*min(cycle)), sum(cycle)+min(cycle)+((len(cycle)+1)*min(arr)))
    return cost
n = int(input())
w = list(map(int, input().split()))
print(minimumCostSort(w, n))

Submission status: Accepted

Solution code:
n = int(input())
n_lst = list(map(int, input().split()))
sorted_lst = sorted(n_lst)
cost = 0

for i in range(n):
    a = n_lst.index(sorted_lst[i])
    j = 0
    while a > i:
        j += 1
        b = n_lst.index(sorted_lst[a])
        cost += n_lst[b]
        n_lst[a],n_lst[b] = n_lst[b],n_lst[a]
        a = b
    cost += min(sorted_lst[i]*j,sorted_lst[i]*2+sorted_lst[0]*(j+2))
print(cost)

Submission status: Accepted

Solution code:
# Minimum cost sort

n = int(input())
*w, = map(int, input().split())
s = list(sorted(w))

si = [0] * 10001
for i, v in enumerate(s):
    si[v] = i

ans = 0
b = [False] * n
for i in range(n):
    if b[i]:
        continue
    j = i
    mw = w[i]
    z = 0
    nn = 0
    while b[j] == False:
        b[j] = True
        nn += 1
        mw = min(w[j], mw)
        z += w[j]
        j = si[w[j]]
    c = min((nn - 2) * mw + z, mw + z + (nn + 1) * s[0])
    ans += c

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

n = int(input().rstrip())
wi = [int(i) for i in input().rstrip().split()]
visited = [False for i in range(n)]
minw = min(wi)
dict = {}
for i, v in enumerate(sorted(wi)):
    dict[v] = i

ans = 0
for i in range(n):
    if visited[i]:
        continue
    cnt = 0
    now = i
    mi = 100000
    s = 0
    while True:
        if visited[now]:
            break
        cnt += 1
        visited[now] = True
        mi = min(mi, wi[now])
        s += wi[now]
        now = dict[wi[now]]
    
    tmp = s + (cnt-2)*mi
    tmp = min(tmp, s+mi+minw*(cnt+1))
    ans += tmp

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

W_MAX = 10000

n = int(stdin.readline().rstrip())
w = [int(x) for x in stdin.readline().rstrip().split()]
min_w = min(w)
idx = {}
for i, wi in enumerate(sorted(w)):
    idx[wi] = i

isVisited = [False]*n
cost = 0
for i in range(n):
    if isVisited[i]:
        continue

    cur = i
    cyc = []
    min_cyc = W_MAX
    while not isVisited[cur]:
        isVisited[cur] = True
        cyc.append(w[cur])
        min_cyc = min(min_cyc, w[cur])
        cur = idx[w[cur]]

    cost += min(sum(cyc) + (len(cyc)-2)*min_cyc, sum(cyc) + (len(cyc)+1)*min_w + min_cyc)

print(cost)

Submission status: Accepted

Solution code:
def silly_sort(target):
    ranked = sorted(target)
    length = len(target)
    rings = [n for n in range(length)]
    all_cost = 0
    minimum = ranked[0]
    base_index = {}
    rank_index = {}
    for i, (t, r) in enumerate(zip(target, ranked)):
        base_index[t] = i
        rank_index[r] = i
    for i in range(length):
        if rings[i] != -1 and target[i] != ranked[i]:
            ring_sum = target[i]
            min_m = target[i]
            num_ring = 1
            next_index = rank_index[target[i]]
            next_num = target[next_index]
            while next_index != i:
                # print(i, next_index, target[i], min_m, ring_sum)
                num_ring += 1
                ring_sum += next_num
                min_m = min(min_m, next_num)
                rings[next_index] = -1
                next_index = rank_index[target[next_index]]
                next_num = target[next_index]
            # print(min((ring_sum + min_m * (num_ring - 2) ), (ring_sum + min_m + minimum * (num_ring + 1) ) ))
            all_cost += min((ring_sum + min_m * (num_ring - 2) ), (ring_sum + min_m + minimum * (num_ring + 1) ) )
        rings[i] = -1
    return all_cost

l = int(input())
t = [int(n) for n in input().split(" ")]
print(silly_sort(t))

Submission status: Accepted

Solution code:
def solve(a,n,mn,mx):
	ans=0
	V=[False]*n
	b=sorted(a)
	T=[0]*(mx+1)
	for i in range(n): T[b[i]]=i
	for i in range(n):
		if V[i]: continue
		cur=i
		sum=0
		cnt=0
		m=1<<30
		while True:
			V[cur]=True
			v=a[cur]
			cnt+=1
			sum+=v
			m=min(m,v)
			cur=T[v]
			if V[cur]: break
		ans+=min(sum+(cnt-2)*m,sum+m+(cnt+1)*mn)
	return ans

n=int(input())
a=list(map(int,input().split()))
mn=1<<30
mx=mn*-1
for i in range(n):
	mn=min(mn,a[i])
	mx=max(mx,a[i])
print(solve(a,n,mn,mx))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    array = [int(x) for x in input().split()]
    sorted_array = sorted(array)

    groups = []
    for i in range(len(array)):
        moving_src_val = array[i]
        if not moving_src_val:
            continue
        group = [moving_src_val]
        while True:
            moving_tgt_idx = sorted_array.index(moving_src_val)
            moving_tgt_val = array[moving_tgt_idx]
            if moving_tgt_val in group:
                break
            group.append(moving_tgt_val)
            array[moving_tgt_idx] = False
            moving_src_val = moving_tgt_val
        array[i] = False
        groups.append(group)

    #print(groups)

    min_cost = 0
    min_in_array = sorted_array[0]
    for group in groups:
        n_group = len(group)
        if n_group == 1:
            continue
        min_in_group = min(group)
        sum_without_min = sum(group) - min_in_group

        cost1 = (n_group - 1) * min_in_group
        cost2 = (n_group + 1) * min_in_array + 2 * min_in_group

        if cost1 < cost2:
            min_cost += cost1 + sum_without_min
        else:
            min_cost += cost2 + sum_without_min

    print(min_cost)
    return


main()

Submission status: Accepted

Solution code:
n=int(input())
data=list(map(int,input().split()))

sorted_data=sorted(data)
mindata=sorted_data[0]

data_dict={}
for i in range(n):
    data_dict[data[i]]=i#key：データに含まれる要素　value:そのデータのインデックス

sorted_data_dict={}
for i in range(n):
    sorted_data_dict[sorted_data[i]]=i


swap_cost=0


for x in sorted_data:
    if(sorted_data_dict[x]!=data_dict[x]):
        tmp_cost=0
        swap_num=0

        while(sorted_data_dict[x]!=data_dict[x]):
            ind1=data_dict[x]
            ind2=data_dict[sorted_data[ind1]]
            data_dict[x]=ind2
            data_dict[sorted_data[ind1]]=ind1
            tmp_cost+=x+sorted_data[ind1]
            swap_num+=1
        if( (x+mindata)*2 < swap_num*(x-mindata) ):
            tmp_cost+=(x+mindata)*2 - swap_num*(x-mindata)
        swap_cost+=tmp_cost

print(swap_cost)

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.readline())
w = list(map(int, sys.stdin.readline().split()))
c = [False]*n
u = sorted(w)
cost = 0
while False in c:
    i = c.index(False)
    c[i] = True
    i0=i
    llen=1
    lmin=w[i]
    while True:
        i = u.index(w[i])
        if c[i]: break
        c[i] = True
        llen+=1
        if lmin > w[i]: lmin = w[i]
        cost += w[i]

    if llen>1:
        cost += w[i0]+min(lmin+(llen+1)*min(w), lmin*(llen-2))

print(cost)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = sorted(a)
c = 0
for i in range(n - 1):
    t = cnt = 0
    # 動かす数字の位置
    x = a.index(b[i])
    while x != i:
        # 動かす数字の所にあるべき数字
        y = a.index(b[x])
        # a[x], a[y] = b[x], b[i]
        a[x], a[y] = a[y], a[x]
        cnt += 1
        # t += b[x] + b[i]
        t += a[x] + a[y]
        x = y
    if cnt:
        c += min(t, (b[i] + b[0]) * 2 + t - (b[i] - b[0]) * cnt)
print(c)

Submission status: Accepted

Solution code:
def solve(a, n):
    vmax = 10000
    ans = 0
    all_min = min(a)
    b = sorted(a)
    v = [False] * n

    t = {}
    for i in range(n):
        t[b[i]] = i
    for i in range(n):
        if v[i]:
            continue
        cur = i
        w_sum = 0
        w_min = vmax
        an = 0
        while True:
            v[cur] = True
            an += 1
            v_cur = a[cur]
            w_min = min(w_min, v_cur)
            w_sum += v_cur
            cur = t[v_cur]
            if v[cur]:
                break
        ans += min(w_sum + (an-2) * w_min, w_min + w_sum + (an+1) * all_min)

    return ans


n = int(input())
a = [int(v) for v in input().split()]

ans = solve(a, n)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = [int(i) for i in input().split()]
B = A.copy()
B.sort()
ans = 0
for i in B:
    ixB = B.index(i)
    counter = 0
    while(True):
        ixA = A.index(i)
        if ixA == ixB:
            break
        else:
            counter += 1
            num = B[ixA]
            ixN = A.index(num)
            A[ixA],A[ixN] = A[ixN],A[ixA]
            ans += A[ixA] + A[ixN]
    tmp = (B[0] - i)*counter + (B[0]+i)*2
    if tmp < 0:
        ans += tmp
print(ans)