# coding: utf-8
import numpy as np
N = raw_input()
L = raw_input()
N, L = map(int, N.split())[0],np.array(map(int, L.split()))
cost = 0
while(1):
argindex = np.argsort(L)
l1 = L[argindex[0]]
l2 = L[argindex[1]]
L = np.delete(L, argindex[0])
L = np.delete(L,argindex[1]-1)
cost += l1 + l2
L = np.append(L, l1 + l2)
if len(L) ==1:
break
print cost
argmin (0) and argmin (1) were good.
It may be better to write articles for each chapter instead of each question.
The point is ・ No matter how you cut, the final number of cuts does not change. ・ Each cut divides the board into independent blocks ・ Cost is proportional to the depth at which the board is cut out in each block.
Therefore, in the case of L = {a, b, c} (a <= b <= c), it is best to cut out c alone, and the cost is (a + b + c) + (a + b).
If the number of elements of L is odd, the deepest part of the tree will look like this, so you can pair a and b.
When the number of elements of L is even When L = {a, b, c, d} (a <= b <= c <= d), when comparing the cost of cutting out two parts-> two parts and d
2(a + b + c + d )
When
(a + b + c + d) + (a + b + c) + (a + b) = 3(a+b) + 2c + d
It cannot be said unconditionally which is correct (depending on the values of a, b, and d).
However, in either case, a and b are the final pair at the lowest cost.
If a and b are paired (ab), Since it becomes a board of L = {ab, c, d}, it can be reduced to an odd number, and the next combination is L = {abc, d}.
Even if L = {a, b, c, d, e} is considered when the number of elements is 5, a and b are always paired at the minimum cost, so it can be finally dropped when it is 3.
So, if you make a pair of the smallest two, it's ok.
Recommended Posts