# 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) et argmin (1) étaient bons.
Il peut être préférable d'écrire des articles pour chaque chapitre plutôt que pour chaque question.
Le point est ・ Peu importe la façon dont vous coupez, le nombre final de coupes ne change pas. ・ Chaque coupe divise la planche en blocs indépendants ・ Le coût est proportionnel à la profondeur à laquelle la découpe de la planche est terminée dans chaque bloc
Par conséquent, dans le cas de L = {a, b, c} (a <= b <= c), il est préférable de couper c seul, et le coût est (a + b + c) + (a + b).
Si le nombre d'éléments de L est impair, la partie la plus profonde de l'arbre ressemblera à ceci, vous pouvez donc associer a et b.
Quand le nombre d'éléments de L est pair Lorsque L = {a, b, c, d} (a <= b <= c <= d), si vous comparez le coût du fractionnement-> fractionnement et découpage d
2(a + b + c + d )
Quand
(a + b + c + d) + (a + b + c) + (a + b) = 3(a+b) + 2c + d
On ne peut pas dire inconditionnellement ce qui est correct (selon les valeurs de a, b et d).
Cependant, dans les deux cas, a et b sont la paire finale au coût le plus bas.
Si a et b sont appariés (ab), Puisqu'il devient un tableau de L = {ab, c, d}, il peut être réduit à un nombre impair, et la combinaison suivante est L = {abc, d}
Même si L = {a, b, c, d, e} est considéré lorsque le nombre d'éléments est de 5, a et b sont toujours appariés au coût minimum, donc il peut être finalement abandonné lorsque 3.
Donc, si vous faites une paire des deux plus petits, ça va.
Recommended Posts