L'idée, c'est de trouver la hauteur y du câble central qui permet de minimiser la somme des distances au câble central. Il se trouve que la médiane permet d'atteindre ce minimum. C'est pas forcément intuitif, mais une fois qu'on sait que c'est la médiane, ça se démontre. Quand il y a 2 médianes (nb pair de valeurs), toutes les valeurs entre ces 2 médianes atteignent le minimum. Et hier une simple recherche sur "minimiser somme des valeurs absolue" m'a permis de trouver que c'était la médiane.
Donc tu calcules la médiane des y, tu calcules la somme |y[i]-median(y)| et tu ajoutes x_max-x_min pour la longueur du câble central.
# Principe de l'algo
Posté par BeberKing . En réponse au message exercices donnés au codinggame n°2. Évalué à 3.
L'idée, c'est de trouver la hauteur y du câble central qui permet de minimiser la somme des distances au câble central. Il se trouve que la médiane permet d'atteindre ce minimum. C'est pas forcément intuitif, mais une fois qu'on sait que c'est la médiane, ça se démontre. Quand il y a 2 médianes (nb pair de valeurs), toutes les valeurs entre ces 2 médianes atteignent le minimum. Et hier une simple recherche sur "minimiser somme des valeurs absolue" m'a permis de trouver que c'était la médiane.
Donc tu calcules la médiane des y, tu calcules la somme |y[i]-median(y)| et tu ajoutes x_max-x_min pour la longueur du câble central.