Kabel verbinden
Sie haben
n Kabel mit bestimmten Längen und möchten daraus ein einziges, durchgehendes Kabel herstellen. Um zwei Kabel mit Längen x und y zu verbinden, müssen Sie x + y bezahlen. Nach diesem Verbinden entsteht ein neues Kabel mit der Länge x + y.Die Frage lautet: Wie viel müssen Sie insgesamt mindestens bezahlen, um alle Kabel zu einem einzigen Kabel zu verbinden?
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ ), die angibt, wie viele Kabel vorhanden sind.In der zweiten Zeile stehen durch Leerzeichen getrennt die Längen (1 ≤ ≤ ).
Ausgabe
Das Programm soll den minimalen Betrag ausgeben, der benötigt wird, um alle Kabel miteinander zu verbinden.
Beispiele
Eingabe | Ausgabe |
5
1 2 3 6 2 | 30 |
Erklärung
- Verbinden Sie 1 und 2 ⇒ Kosten 3 ⇒ 3 3 6 2
- Verbinden Sie 2 und 3 ⇒ Kosten 5 ⇒ 5 3 6
- Verbinden Sie 3 und 5 ⇒ Kosten 8 ⇒ 6 8
- Verbinden Sie 6 und 8 ⇒ Kosten 14
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB