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