Connecter les câbles
Étant donné n câbles avec leurs longueurs, vous souhaitez relier tous ces câbles pour n’en former qu’un seul. Pour connecter deux câbles de longueurs x et y, vous devez payer x + y. Une fois assemblés, le nouveau câble a une longueur de x + y.
Quel est le montant minimal que vous devrez dépenser pour relier tous les câbles ?
Entrée
La première ligne de l’entrée contient un entier n (1 ≤ n ≤ ), qui correspond au nombre de câbles.
La ligne suivante contient des entiers séparés par des espaces (1 ≤ ≤ ). Chacun de ces entiers représente la longueur d’un câble.
Sortie
Le programme doit afficher le montant minimal à dépenser pour connecter tous les câbles.
Exemples
Entrée | Sortie |
|---|---|
5 1 2 3 6 2 | 30 |
Explication
Connecter 1 et 2 ⇒ payer 3 ⇒ 3 3 6 2
Connecter 2 et 3 ⇒ payer 5 ⇒ 5 3 6
Connecter 3 et 5 ⇒ payer 8 ⇒ 6 8
Connecter 6 et 8 ⇒ payer 14
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB