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: Wrong Answer

Solution code:
def swap(a, b):
    return (b, a)


def selectionSortWithCosts(array):
    n = len(array)
    cost = 0
    for i in range(n):
        minimumElement = min(array[i:])
        if minimumElement == array[i]:
            continue
        else:
            indexOfTheMinimumElement = array.index(minimumElement)
            swappedElements = swap(array[i], array[indexOfTheMinimumElement])
            array[i] = swappedElements[0]
            array[indexOfTheMinimumElement] = swappedElements[1]
            cost += sum(swappedElements)

    return {"cost": cost, "sortedArray": array}


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

print(selectionSortWithCosts(array)["cost"])

Submission status: Wrong Answer

Solution code:
#! /usr/local/bin/python3
# coding: utf-8

from bisect import bisect_left


def swap(w, i, j):
    tmp = w[i]
    w[i] = w[j]
    w[j] = tmp


def min_weight(w):
    ws = sorted(w)
    weight = 0
    for i in reversed(range(len(w))):
        j = bisect_left(ws, w[i])
        if i != j:
            weight += w[i] + w[j]
            swap(w, i, j)
    return weight


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


main()

Submission status: Wrong Answer

Solution code:
#! /usr/local/bin/python3
# coding: utf-8

from bisect import bisect_left


def swap(w, i, j):
    tmp = w[i]
    w[i] = w[j]
    w[j] = tmp


def min_weight(w):
    ws = sorted(w)
    # print(ws)
    # print(w)
    weight = 0
    for i in reversed(range(len(w))):
        j = w.index(ws[i])
        # print(i, j)
        if i != j:
            weight += w[i] + w[j]
            swap(w, i, j)
        # print(ws)
        # print(w)
    return weight


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


main()

Submission status: Wrong Answer

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
    #本来i番目にいるべき値はaではどこにいるのか（ループの最小値）
    x = a.index(b[i])
    #もしあるべき場所にあったり、あるべき場所に帰ってきたら終了
    while x != i:
        #ループで最も小さい値を使いまわしながら整えていく
        #ループの最小値が入っている場所にいるべき値がaでは何処にいるか
        y = a.index(b[x])
        #a[x]とa[y]を入れ替えればよい
        a[x],a[y] = a[y],a[x];cnt += 1
        t += a[x] + a[i]
        x = y
    if cnt: c += min(t, (b[i]+b[0])*2 + t -(b[i]-b[0])*cnt)
print(c)
# print(a)

Submission status: Wrong Answer

Solution code:
import itertools


WAIT, PRESORT, SORTED = 0, 1, 2
cost = 0

def swap(w1, w2):
    global cost
    cost += w1[WAIT] + w2[WAIT]
    w1[PRESORT], w2[PRESORT] = w2[PRESORT], w1[PRESORT]

n = input()
w = [[wi, i, None] for i, wi in enumerate(map(int, input().split()))]
s = sorted(w)

for i, wi in enumerate (s):
    wi[SORTED] = i

for si in s:
    tmp = si
    t = []
    while tmp[SORTED] != si[PRESORT]:
        tmp = w[tmp[SORTED]]
        t += [tmp]
    
    for ti in t[::-1]:
        swap(si, ti)

print(cost)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

cache = {}


def remaining_expected_cost(a):
    global n, b, cache
    key = tuple(i for i in range(n) if a[i] != b[i])
    if key in cache:
        return cache[key]
    return sum(a[i] for i in key)


def stack(node):
    global heap, n
    for i in range(n - 1):
        for j in range(i + 1, n):
            swapped = (i, j)
            if swapped == node[2]:
                continue
            a = node[3][:]
            w1, w2 = a[i], a[j] = a[j], a[i]
            spent_cost = node[1] + w1 + w2
            rec = remaining_expected_cost(a)
            if not rec:
                return spent_cost
            heappush(heap, (spent_cost + rec, spent_cost, swapped, a))
    return False


n, a = int(input()), list(map(int, input().split()))
b, m, heap = sorted(a), 0, []

heappush(heap, (remaining_expected_cost(a), 0, None, a))

while heap:
    m = stack(heappop(heap))
    if m is not False:
        break
print(m)

Submission status: Wrong Answer

Solution code:
def perfect_swap():
    global n, a, b, cost
    for i in range(1, n - 1):
        for j in range(i + 1, n):
            ai, aj = a[i], a[j]
            if ai == b[j] and aj == b[i]:
                a[i], a[j] = aj, ai
                cost += ai + aj


def lowest_swap():
    global n, a, b, cost
    for i in range(n - 1):
        bi, tmp_cost, count = b[i], 0, 0
        while a[i] != bi:
            si = a.index(bi)
            bsi = b[si]
            sj = a.index(bsi)
            a[si], a[sj] = bsi, bi
            tmp_cost += bi + bsi
            count += 1
        if count > 0:
            if i > 0:
                bip = b[i - 1]
                cost += min(tmp_cost, (bi + bip) * 2 + tmp_cost - (bi - bip) * count)
            else:
                cost += tmp_cost


n, a, cost = int(input()), list(map(int, input().split())), 0
b = sorted(a)
perfect_swap()
lowest_swap()
print(cost)

Submission status: Wrong Answer

Solution code:
def perfect_swap():
    global n, a, b, cost
    for i in range(1, n - 1):
        for j in range(i + 1, n):
            ai, aj = a[i], a[j]
            if ai == b[j] and aj == b[i]:
                a[i], a[j] = aj, ai
                cost += ai + aj


def lowest_swap():
    global n, a, b, cost
    for i in range(n - 1):
        bi, tmp_cost, count = b[i], 0, 0
        while a[i] != bi:
            si = a.index(bi)
            bsi = b[si]
            sj = a.index(bsi)
            a[si], a[sj] = bsi, bi
            tmp_cost += bi + bsi
            count += 1
        if count:
            if i:
                b0 = b[0]
                cost += min(tmp_cost, (bi + b0) * 2 + tmp_cost - (bi - b0) * count)
            else:
                cost += tmp_cost


n, a, cost = int(input()), list(map(int, input().split())), 0
b = sorted(a)
print(b)
perfect_swap()
lowest_swap()
print(cost)

Submission status: Wrong Answer

Solution code:
"""Minimum cost Sort."""

def min_c_sort(A, n):
    cost = 0
    for i in range(n - 1):
        min_i = i
        for j in range(i + 1, n):
            if A[min_i] > A[j]:
                min_i = j
        if min_i != i:
            cost += A[min_i]
            cost += A[i]
            A[min_i], A[i] = A[i], A[min_i]
    return cost


n = int(input())

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

cost = min_c_sort(A, n)

print(cost)

Submission status: Wrong Answer

Solution code:
"""Minimum cost Sort."""

def min_cost_sort(A):
    """Sort list A in ascending order,

    And return the switching cost in sorting.
    """
    B = list(A)
    B.sort()
    cost = 0
    for i, b in enumerate(B):
        while A.index(b) != i:
            st1 = b
            si1 = A.index(b)
            st2 = B[si1]
            si2 = A.index(st2)
            cost += st1 + st2
            A[si1], A[si2] = st2, st1
    return cost


n = int(input())

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

ans = min_cost_sort(A)

print(ans)

Submission status: Wrong Answer

Solution code:
def get_weights():
    input()
    return map(int, raw_input().split())

#weights: list
def minimam_cost_sort(weights):
    lol = []
    for i in weights:
        if i !=0:
            j = i
            l = [j]
            while weights[j - 1] != 0:
                l.append(weights[j - 1])
                j = weights[j - 1]
                weights[j - 1] = 0
            l.sort()
            lol.append(l)

    lol.sort()
    s = 0
    for l in lol:
        s += get_wol(l)

    print s

def get_wol(l):
    sub = (l[0] - 1) * (len(l) - 1) - (l[0] + 1) * 2
    s = sum(l) + (l[0] * (len(l) - 2))
    if sub > 0:
        return s - sub
    return s

minimam_cost_sort(get_weights())

Submission status: Wrong Answer

Solution code:
def get_weights():
    raw_input()
    return map(int, raw_input().split())

#weights: list
def minimam_cost_sort(weights):
    mw = min(weights)
    s_w = sorted(weights)
    lol = []
    for i in range(len(weights)):
        if weights[i] != 0:
            j = weights[i]
            idx = s_w.index(j)
            weights[i] = 0
            l = [j]
            while weights[idx] != 0:
                l.append(weights[idx])
                j = weights[idx]
                weights[idx] = 0
                idx = s_w.index(j)
            l.sort()
            lol.append(l)

    lol.sort()
    print lol
    s = 0
    for l in lol:
        s += get_wol(l, mw)

    print s

def get_wol(l, mw):
    sub = (l[0] - mw) * (len(l) - 1) - (l[0] + mw) * 2
    s = sum(l) + (l[0] * (len(l) - 2))
    if sub > 0:
        return s - sub
    return s

minimam_cost_sort(get_weights())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import copy

class BagsWithWeight(list):
    def __init__(self, l):
        super(BagsWithWeight, self).__init__(l)
        self.sorted_weights = list(sorted(self))

    def get_lists_of_loop(self):
        """???????????????????????????????????????????±??????????
        ????????\??????????????????????????????????????¬??\???????????? index ???????????????????????????
        ??????????????????????????¬??\???????????? index ????????£???????????¨?????????????????????????????????
        ?????????????????§?????????????????????????????¨ 1 ????????????????????????
        ????????????????????????????????? 1 ????????\???????????§??????????????????????????????????????????
        out: ListOfLoops     ??¨?????? loop ????????????
        """
        c_weights = copy.copy(self)
        loops = Loops()
        for i in range(len(self)):
            loop = []
            index = i
            while c_weights[index] != 0:
                loop.append(c_weights[index])
                c_weights[index] = 0
                index = self.get_index_of_sorted_bag(index)
            if loop:
                loops.append(loop)
        return loops

    def get_index_of_sorted_bag(self, index):
        """???????????????????????????????????????????????? index ????????????
        in:  index    int    ??????????????? index ????±?????????????????????? index
        out: int    ?????????????????????????????? index
        """
        return self.sorted_weights.index(self[index])


class Loops(list):
    def append(self, elm):
        elm.sort()
        elm = Loop(elm, self)
        super(Loops, self).append(elm)

    def get_minimum_element(self):
        return min(min(self))

    def get_cost(self):
        return sum(map((lambda loop: loop.get_cost_of_sorting()), self))


class Loop(list):
    def __init__(self, loop, loops):
        super(Loop, self).__init__(loop)
        self.loops = loops
    
    def get_minimum_weight_of_outer(self):
        return self.loops.get_minimum_element()

    def get_cost_of_sorting(self):
        """Loop ?????¨???????°??????????????±??????????
        """
        cost = sum(self) + min(self) * (len(self) - 2)
        cost_reduced = self.get_how_much_outer_minimum_weight_bag_reduces_cost()
        if cost_reduced > 0:
            return cost - cost_reduced
        else:
            return cost


    def get_how_much_outer_minimum_weight_bag_reduces_cost(self):
        """Loops ???????°????????????????????????£???????????§???????????????????±??????????
        List of Loops ??????????°?????????????????´????
        Loop ??????????°?????????????????´???¨??\????????????
        ?????????????????£?????????????????§???????????????????????????
        ??????????????? len(loop) - 1 ??????????????????????????????????°???????????????????????????????
        out: int    ????????§???????????????
        """
        return ((min(self) - self.get_minimum_weight_of_outer()) *
                    (len(self) - 1) -
                    (min(self) + self.get_minimum_weight_of_outer()) * 2)


def get_weights():
    raw_input()
    return map(int, raw_input().split())

bww = BagsWithWeight(get_weights())
loops = bww.get_lists_of_loop()
print loops.get_cost()

Submission status: Wrong Answer

Solution code:
"""Minimum cost Sort."""

def make_cycle(A):
    """Return a list which has the minimum element of A and
    switch elements cycles as list.

    A is a list whose elements' type is 'int'.
    """
    B = list(A)
    B.sort()
    cycle_list = [B[0]]
    for i, b in enumerate(B):
        if b:
            new_cycle = []
            new_cycle.append(b)
            B[i] = None
            si = A.index(b)
            while si != i:
                st = B[si]
                new_cycle.append(st)
                B[si] = None
                si = A.index(st)
            cycle_list.append(new_cycle)
    return cycle_list

def min_sorting_cost(A):
    """Return the minimum cost of sorting A.

    A is a list whose elements' type is 'int'.
    """
    cycles = make_cycle(A)
    min_w = cycles[0]
    cost = 0
    for c in cycles[1:]:
        n = len(c)
        min_cw = c[0]
        dec = (n - 1) * (min_cw - min_w)
        inc = 2 * (min_w + min_cw)
        if dec < inc:
            cost += sum(c) + min_cw * (n - 2)
        else:
            cost += sum(c) + min_cw * (n - 2) - dec + inc
    return cost


n = int(input())

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

ans = min_sorting_cost(A)

print(ans)

Submission status: Wrong Answer

Solution code:
def mincost_sort(ws):
    cost = 0
    for i in range(len(ws) - 1, 0, -1):
        imax = i
        for j in range(i - 1, -1, -1):
            if ws[j] > ws[imax]:
                imax = j
        if imax != i:
            ws[imax], ws[i] = ws[i], ws[imax]
            cost += ws[imax] + ws[i]
    return cost


input()
ws = list(map(int, input().split()))
print(mincost_sort(ws))

Submission status: Wrong Answer

Solution code:
n, cost = int(input()), 0
num = list(map(int, input().split()))
num_s = sorted(num)
n0 = num[0]

for i in range(n - 1):
    ni, tmp, cnt = num_s[i], 0, 0
    si = num.index(ni)
    while si != i:
        nsi = num_s[si]
        sj = num.index(nsi)
        num[si], num[sj] = nsi, ni
        tmp += ni + nsi
        cnt += 1
        si = sj
    if cnt:
        cost += min((ni + n0) * 2 + tmp - (ni - n0) * cnt, tmp)
print(cost)

Submission status: Wrong Answer

Solution code:
n, cost = int(input()), 0
num = list(map(int, input().split()))
num_s = sorted(num)
n0 = num[0]

for i in range(n - 1):
    ni, tmp, cnt = num_s[i], 0, 0
    si = num.index(ni)
    while si != i:
        nsi = num_s[si]
        sj = num.index(nsi)
        num[si], num[sj] = nsi, ni
        tmp += ni + nsi
        cnt += 1
        si = sj
    if cnt:
        cost += min(tmp, (ni + n0) * 2 + tmp - (ni - n0) * cnt)
print(cost)

Submission status: Wrong Answer

Solution code:
n=int(input())
array=[int(i) for i in input().split()]
temp=array.copy()
array.sort()
w=0
for i in range(n):
    for j in range(n):
        if i!=j and temp[i]==array[j]:
            array[i],array[j]=array[j],array[i]
            w+=array[i]
            w+=array[j]
print(w)

Submission status: Wrong Answer

Solution code:
n=int(input())
array=[int(i) for i in input().split()]
temp=array.copy()
array.sort()
w=0
for i in range(1,1+n):
    for j in range(1,1+n):
        if i!=j and array[n-i]==temp[n-j]:
            temp[n-i],temp[n-j]=temp[n-j],temp[n-i]
            w+=temp[n-i]
            w+=temp[n-j]
print(w)

Submission status: Wrong Answer

Solution code:
def partition(target_list, l, r):
    x = target_list[r]
    i = l - 1

    for j in range(l, r):
        if target_list[j] <= x:
            i = i + 1
            tmp = target_list[i]
            target_list[i] = target_list[j]
            target_list[j] = tmp
    tmp = target_list[r]
    target_list[r] = target_list[i + 1]
    target_list[i + 1] = tmp
    
    return  i + 1

def quick_sort(target_list, l, r):
    if l < r:
        c = partition(target_list, l, r)
        quick_sort(target_list, l, c - 1)
        quick_sort(target_list, c + 1, r)
        
def minimum_cost_sort(target_list):
    correct_list = [a for a in target_list]
    quick_sort(correct_list, 0, len(correct_list) - 1)
    cost = 0
    i = 0
    while not correct_list == target_list:
        if target_list.index(correct_list[i]) == i:
            i += 1
        else:
            min_i = target_list.index(correct_list[i])
            change_i = correct_list.index(target_list[min_i])
            cost += (target_list[min_i] + target_list[change_i])
            tmp = target_list[min_i]
            target_list[min_i] = target_list[change_i]
            target_list[change_i] = tmp
            
    return cost
def main():
    n_list = input()
    target_list = [int(s) for s in input().split()]
    print(minimum_cost_sort(target_list))
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_D
#????°???????????????????
def partition(target_list, l, r):
    x = target_list[r]
    i = l - 1

    for j in range(l, r):
        if target_list[j] <= x:
            i = i + 1
            tmp = target_list[i]
            target_list[i] = target_list[j]
            target_list[j] = tmp
    tmp = target_list[r]
    target_list[r] = target_list[i + 1]
    target_list[i + 1] = tmp
    
    return  i + 1

def quick_sort(target_list, l, r):
    if l < r:
        c = partition(target_list, l, r)
        quick_sort(target_list, l, c - 1)
        quick_sort(target_list, c + 1, r)
        
def minimum_cost_sort(target_list):
    correct_list = [a for a in target_list]
    quick_sort(correct_list, 0, len(correct_list) - 1)
    cost = 0
    i = 0
    while not correct_list == target_list:
        if target_list.index(correct_list[i]) == i:
            i += 1
        else:
            min_i = target_list.index(correct_list[i])
            change_i = target_list.index(correct_list[min_i])
            cost += (target_list[min_i] + target_list[change_i])
            tmp = target_list[min_i]
            target_list[min_i] = target_list[change_i]
            target_list[change_i] = tmp
    return cost
def main():
    n_list = input()
    target_list = [int(s) for s in input().split()]
    print(minimum_cost_sort(target_list))
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_D
#????°???????????????????
def partition(target_list, l, r):
    x = target_list[r]
    i = l - 1

    for j in range(l, r):
        if target_list[j] <= x:
            i = i + 1
            tmp = target_list[i]
            target_list[i] = target_list[j]
            target_list[j] = tmp
    tmp = target_list[r]
    target_list[r] = target_list[i + 1]
    target_list[i + 1] = tmp
    
    return  i + 1

def quick_sort(target_list, l, r):
    if l < r:
        c = partition(target_list, l, r)
        quick_sort(target_list, l, c - 1)
        quick_sort(target_list, c + 1, r)
        
def minimum_cost_sort(target_list):
    correct_list = [a for a in target_list]
    quick_sort(correct_list, 0, len(correct_list) - 1)
    cost = 0
    i = 0
    while not correct_list == target_list:
        if target_list.index(correct_list[i]) == i:
            i += 1
        else:
            min_i = target_list.index(correct_list[i])
            change_i = target_list.index(correct_list[min_i])
            cost += (target_list[min_i] + target_list[change_i])
            tmp = target_list[min_i]
            target_list[min_i] = target_list[change_i]
            target_list[change_i] = tmp
        print(target_list)
    return cost
def main():
    n_list = input()
    target_list = [int(s) for s in input().split()]
    print(minimum_cost_sort(target_list))
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_D
#????°???????????????????
def partition(target_list, l, r):
    x = target_list[r]
    i = l - 1

    for j in range(l, r):
        if target_list[j] <= x:
            i = i + 1
            tmp = target_list[i]
            target_list[i] = target_list[j]
            target_list[j] = tmp
    tmp = target_list[r]
    target_list[r] = target_list[i + 1]
    target_list[i + 1] = tmp
    
    return  i + 1

def quick_sort(target_list, l, r):
    if l < r:
        c = partition(target_list, l, r)
        quick_sort(target_list, l, c - 1)
        quick_sort(target_list, c + 1, r)
        
def minimum_cost_sort(target_list):
    correct_list = [a for a in target_list]
    quick_sort(correct_list, 0, len(correct_list) - 1)
    cost = 0
    i = 0
    while not correct_list == target_list:
        if target_list.index(correct_list[i]) == i:
            i += 1
        else:
            min_i = target_list.index(correct_list[i])
            change_i = target_list.index(correct_list[min_i])
            cost += (target_list[min_i] + target_list[change_i])
            tmp = target_list[min_i]
            target_list[min_i] = target_list[change_i]
            target_list[change_i] = tmp
        #print(target_list)
    return cost
def main():
    n_list = input()
    target_list = [int(s) for s in input().split()]
    print(minimum_cost_sort(target_list))
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_D
#????°???????????????????
def partition(target_list, l, r):
    x = target_list[r]
    i = l - 1

    for j in range(l, r):
        if target_list[j] <= x:
            i = i + 1
            tmp = target_list[i]
            target_list[i] = target_list[j]
            target_list[j] = tmp
    tmp = target_list[r]
    target_list[r] = target_list[i + 1]
    target_list[i + 1] = tmp
    
    return  i + 1

def quick_sort(target_list, l, r):
    if l < r:
        c = partition(target_list, l, r)
        quick_sort(target_list, l, c - 1)
        quick_sort(target_list, c + 1, r)

def processA(target_list, correct_list, i):

    cost = 0
    while not correct_list[i] == target_list[i]:
        min_i = target_list.index(correct_list[i])
        change_i = target_list.index(correct_list[min_i])
        cost += (target_list[min_i] + target_list[change_i])
        target_list[min_i], target_list[change_i] = target_list[change_i], target_list[min_i]

    return cost
    
def processB(target_list, correct_list, i):
    most_min = correct_list[0]
    second_min = correct_list[i]
    cost = (most_min + second_min)
    
    mmi = target_list.index(most_min)
    smi = target_list.index(second_min)
    target_list[mmi], target_list[smi] = target_list[smi], target_list[mmi]
    
    while not correct_list[i] == target_list[i]:
        print(target_list)
        min_i = target_list.index(correct_list[i])
        change_i = target_list.index(correct_list[min_i])
        cost += (target_list[min_i] + target_list[change_i])
        target_list[min_i], target_list[change_i] = target_list[change_i], target_list[min_i]

    return cost
    
def minimum_cost_sort(target_list):
    correct_list = [a for a in target_list]
    quick_sort(correct_list, 0, len(correct_list) - 1)
    cost = 0
    i = 0
    while not correct_list == target_list:
        cost_a = processA(target_list, correct_list, i)
        cost_b = processB([a for a in target_list], correct_list, i)
        cost += min(cost_a, cost_b)
        print(cost_a, cost_b)
        #print(target_list)
        i += 1
    return cost
def main():
    n_list = input()
    target_list = [int(s) for s in input().split()]
    print(minimum_cost_sort(target_list))
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_D
#????°???????????????????
def partition(target_list, l, r):
    x = target_list[r]
    i = l - 1

    for j in range(l, r):
        if target_list[j] <= x:
            i = i + 1
            tmp = target_list[i]
            target_list[i] = target_list[j]
            target_list[j] = tmp
    tmp = target_list[r]
    target_list[r] = target_list[i + 1]
    target_list[i + 1] = tmp
    
    return  i + 1

def quick_sort(target_list, l, r):
    if l < r:
        c = partition(target_list, l, r)
        quick_sort(target_list, l, c - 1)
        quick_sort(target_list, c + 1, r)

def processA(target_list, correct_list, i):

    cost = 0
    while not correct_list[i] == target_list[i]:
        min_i = target_list.index(correct_list[i])
        change_i = target_list.index(correct_list[min_i])
        cost += (target_list[min_i] + target_list[change_i])
        target_list[min_i], target_list[change_i] = target_list[change_i], target_list[min_i]

    return cost
    
def processB(target_list, correct_list, i):
    most_min = correct_list[0]
    second_min = correct_list[i]
    cost = (most_min + second_min)
    
    mmi = target_list.index(most_min)
    smi = target_list.index(second_min)
    target_list[mmi], target_list[smi] = target_list[smi], target_list[mmi]
    
    while not correct_list[i] == target_list[i]:
        #print(target_list)
        min_i = target_list.index(correct_list[i])
        change_i = target_list.index(correct_list[min_i])
        cost += (target_list[min_i] + target_list[change_i])
        target_list[min_i], target_list[change_i] = target_list[change_i], target_list[min_i]

    return cost
    
def minimum_cost_sort(target_list):
    correct_list = [a for a in target_list]
    quick_sort(correct_list, 0, len(correct_list) - 1)
    cost = 0
    i = 0
    while not correct_list == target_list:
        cost_a = processA(target_list, correct_list, i)
        cost_b = processB([a for a in target_list], correct_list, i)
        cost += min(cost_a, cost_b)
        print(cost_a, cost_b)
        #print(target_list)
        i += 1
    return cost
def main():
    n_list = input()
    target_list = [int(s) for s in input().split()]
    print(minimum_cost_sort(target_list))
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_D
#????°???????????????????
def partition(target_list, l, r):
    x = target_list[r]
    i = l - 1

    for j in range(l, r):
        if target_list[j] <= x:
            i = i + 1
            tmp = target_list[i]
            target_list[i] = target_list[j]
            target_list[j] = tmp
    tmp = target_list[r]
    target_list[r] = target_list[i + 1]
    target_list[i + 1] = tmp
    
    return  i + 1

def quick_sort(target_list, l, r):
    if l < r:
        c = partition(target_list, l, r)
        quick_sort(target_list, l, c - 1)
        quick_sort(target_list, c + 1, r)

def processA(target_list, correct_list, i):

    cost = 0
    while not correct_list[i] == target_list[i]:
        min_i = target_list.index(correct_list[i])
        change_i = target_list.index(correct_list[min_i])
        cost += (target_list[min_i] + target_list[change_i])
        target_list[min_i], target_list[change_i] = target_list[change_i], target_list[min_i]
    return cost
    
def processB(target_list, correct_list, i):
    minv = correct_list[0]
    target = correct_list[i]
    if minv == target:
        return 0
    cost = (minv + target)
    
    mmi = target_list.index(minv)
    smi = target_list.index(target)
    target_list[mmi], target_list[smi] = target_list[smi], target_list[mmi]
    
    while not correct_list[i] == target_list[i]:
        min_i = target_list.index(correct_list[i])
        change_i = target_list.index(correct_list[min_i])
        cost += (target_list[min_i] + target_list[change_i])
        target_list[min_i], target_list[change_i] = target_list[change_i], target_list[min_i]
    return cost
    
def minimum_cost_sort(target_list):
    correct_list = [a for a in target_list]
    quick_sort(correct_list, 0, len(correct_list) - 1)
    cost = 0
    i = 0
    while not correct_list == target_list:
        cost_b = processB([a for a in target_list], correct_list, i)
        cost_a = processA(target_list, correct_list, i)
        cost += min(cost_a, cost_b)
        #print(cost_a, cost_b)
        #print(target_list)
        i += 1
    return cost
def main():
    n_list = input()
    target_list = [int(s) for s in input().split()]
    print(minimum_cost_sort(target_list))
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_D
#????°???????????????????
def partition(target_list, l, r):
    x = target_list[r]
    i = l - 1

    for j in range(l, r):
        if target_list[j] <= x:
            i = i + 1
            tmp = target_list[i]
            target_list[i] = target_list[j]
            target_list[j] = tmp
    tmp = target_list[r]
    target_list[r] = target_list[i + 1]
    target_list[i + 1] = tmp
    
    return  i + 1

def quick_sort(target_list, l, r):
    if l < r:
        c = partition(target_list, l, r)
        quick_sort(target_list, l, c - 1)
        quick_sort(target_list, c + 1, r)

def processA(target_list, correct_list, i):

    cost = 0
    while not correct_list[i] == target_list[i]:
        min_i = target_list.index(correct_list[i])
        change_i = target_list.index(correct_list[min_i])
        cost += (target_list[min_i] + target_list[change_i])
        target_list[min_i], target_list[change_i] = target_list[change_i], target_list[min_i]
        print("A", target_list)
    return cost
    
def processB(target_list, correct_list, i):
    minv = correct_list[0]
    target = correct_list[i]

    if minv == target:
        return 10 ** 9
    cost = (minv + target)
    
    mmi = target_list.index(minv)
    smi = target_list.index(target)
    target_list[mmi], target_list[smi] = target_list[smi], target_list[mmi]
    
    while not correct_list[i] == target_list[i]:
        min_i = target_list.index(correct_list[i])
        change_i = target_list.index(correct_list[min_i])
        cost += (target_list[min_i] + target_list[change_i])
        target_list[min_i], target_list[change_i] = target_list[change_i], target_list[min_i]
        print("B",target_list)
    return cost
    
def minimum_cost_sort(target_list):
    correct_list = [a for a in target_list]
    quick_sort(correct_list, 0, len(correct_list) - 1)
    cost = 0
    i = 0
    while not correct_list == target_list:
        cost_b = processB([a for a in target_list], correct_list, i)
        cost_a = processA(target_list, correct_list, i)
        cost += min(cost_a, cost_b)
        print(cost_a, cost_b)
        #print(target_list)
        i += 1
    return cost
def main():
    n_list = input()
    target_list = [int(s) for s in input().split()]
    print(minimum_cost_sort(target_list))
    
if __name__ == "__main__":
    main()