Rendre les hauteurs uniformes
Afin de réduire les dépenses, le service d’urbanisme vous demande d’uniformiser la taille de tous les immeubles. Avoir des immeubles de hauteur identique permettra de diminuer considérablement les coûts de construction.
Ils ont réuni n immeubles dans la ville, chacun avec une hauteur différente . Modifier la hauteur d’un immeuble de x provoque une réunion qui dure x minutes. Comme vous êtes très occupé, vous cherchez à minimiser la durée totale de ces réunions. Quel est le temps minimal possible à passer en réunions?
Entrée
La première ligne de l’entrée contient un entier n (1 ≤ n ≤ ).
La ligne suivante contient n entiers séparés par des espaces (1 ≤ ≤ ) représentant les hauteurs initiales des immeubles.
Sortie
Le programme doit afficher un seul entier : le temps minimal total passé en réunions.
Exemples
Entrée | Sortie |
|---|---|
5 1 4 8 2 9 | 14 |
Explication
La hauteur optimale est 4 ⇒ nous devons modifier 1 → 4 (réunion de 3 minutes), 2 → 4 (réunion de 2 minutes), 8 → 4 (réunion de 4 minutes) et 9 → 4 (réunion de 5 minutes) ⇒ un total de 14 minutes.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB