Das Problem hierbei ist, eine Menge aller ganzzahligen Punkte zu finden, die eine minimale Summe aller Manhattan-Entfernungen von einer gegebenen Menge von Punkten ergibt!

Zum Beispiel:

Lässt eine gegebene Menge von Punkten haben {P1, P2, P3 ... Pn}

Das Grundproblem besteht darin, einen Punkt zu finden, der über alle Entfernungen von den Punkten {P1, P2, P3 ... Pn} eine minimale Summe hat.

| P1-X | + | P2-X | + .... + | Pn-X | = D, wobei D über alle X minimal ist.

Um einen Schritt weiter zu gehen, kann es mehr als einen Wert von X geben, der die obige Bedingung erfüllt. es kann mehr als ein X möglich sein, das den gleichen Wert D ergibt. Wir müssen also alle diese X finden.

Ein grundlegender Ansatz, den sich jeder vorstellen kann, besteht darin, den Median der Eingaben zu finden und dann die Koordinaten zu erzwingen, die in erwähnt werdendieser Beitrag

Das Problem bei einem solchen Ansatz ist jedoch: Wenn der Median zwei Werte angibt, die sehr weit voneinander entfernt sind, erzwingen wir am Ende alle Punkte, die in einer bestimmten Zeit niemals ablaufen werden.

Gibt es also einen anderen Ansatz, der das Ergebnis auch dann liefert, wenn die Punkte sehr weit voneinander entfernt sind (wobei der Median einen Bereich in der Größenordnung von 10 ^ 9 angibt)?