Farmer John a oublié de réparer un trou dans la clôture ; ses $N$ vaches $(1 \le N \le 1,000)$ se sont échappées et font des ravages ! Chaque minute hors de la clôture, une vache cause un dollar de dégâts. FJ doit aller voir chacune et lui mettre un licol, qui la calmera et arrêtera les dégâts.
Heureusement, elles sont à des positions distinctes sur une droite d'une route hors de la ferme. FJ connaît la position $P_i$ de chaque vache $i$ $(-500,000 \le P_i \le 500,000, P_i \ne 0)$ par rapport au portail (position 0) d'où il part.
FJ avance d'une unité de distance par minute et met un licol instantanément. Déterminez un ordre de visite minimisant le coût total des dégâts ; calculez ce coût minimal.
Entrée
- Ligne 1 : le nombre de vaches $N$.
- Lignes $2\ldots N+1$ : la ligne $i+1$ contient l'entier $P_i$.
Sortie
- Ligne 1 : le coût total minimal des dégâts.
Exemples
Entrée 1
4 -2 -12 3 7
Sortie 1
50
Remarque
Quatre vaches sont aux positions $-2$, $-12$, $3$ et $7$.
L'ordre optimal est $-2,3,7,-12$. FJ arrive en $-2$ en 2 minutes, soit 2 dollars de dégâts pour cette vache.
Il va ensuite en $3$ (distance 5), où les dégâts cumulés de cette vache sont $2 + 5 = 7$ dollars.
Il met encore 4 minutes pour atteindre $7$, avec $7 + 4 = 11$ dollars de dégâts pour cette vache.
Enfin, il met 19 minutes pour aller en $-12$, avec un coût de $11 + 19 = 30$ dollars.
Les dégâts totaux sont $2 + 7 + 11 + 30 = 50$ dollars.
Auteur du problème : Chris Tzamos, 2006