Metoda "dziel i zwyciężaj"

Witam. Mam taki problem do rozwiązania: mam podane punkty ułożone na pewnej prostej i ich odległości od początku tej prostej (tak, prosta nie ma początku, ale to szczegół ;p). Muszę znaleźć punkt, którego suma odległości od pozostałych punktów jest najmniejsza. Przykład:
wejście: 3 -liczba punktów; 5, 15, 10 -odległości kolejnych punktów od początku prostej
wyjście: 3 -nr punktu o najmniejszej sumie, 10 -właśnie ta suma.

Próbowałem dzielić, liczyć sumy odległości dla podprzedziałów i jakoś je porównywać, ale nic mi nie wychodzi. Nie liczę na gotowy kod, ale chociaż jakąś dość jasną do zrozumienia ideę, trochę większą podpowiedź. Za każdą pomoc serdeczne dzięki.

Pomysł na szybko:
Lecimy od początku po posortowanych punktach
Dla pierwszego punktu jego wartość to suma wszystkich wartości pozostałych punktów minus wartość tego pierwszego punktu * ilość pozostałych punktów
Czyli dla 3 -> 5 10 15 wartość dla punktu 5 to: 10+15 - 2*5 = 25 - 10 = 15
Dla każego kolejnego punktu wartość wynosi:
wartość poprzedniego węzła minus różnica wartości poprzedniego węzła i aktualnego węzła (odległość pomiędzy nimi) razy ilość punktów poprawej stronie od poprzedniego węzła, plus odległość między aktualnym węzłem a poprzednim razy ilość węzłów po lewej stronie od aktualnego węzła. Wynika to z tego że aktualny węzeł jest bliżej wszystkich węzłów z prawej strony o dokładnie tyle ile wynosi odległość aktualnego i poprzedniego węzła i jest jednocześnie dalej od węzłów z lewej strony o tą samą odległość ;]
Przy okazji w danym węźle warto zapamiętać ile ma węzłów po prawej i po lewej stronie ale to dość trywialne.
Ale to jest raczej algorytm dynamiczny a nie "dziel i zwiciężaj". Ale ma złożoność O(n) (liniowo obliczamy pierwszy węzeł a potem dla każdego następnego węzła mamy O(1))

Przykład:
5 -> 5, 10, 15, 20, 25

1. Obliczamy pierwszy węzeł:
   10+15+20+25 = 70
   70 - 4*5 = 50
   Więc wartość dla pierwszego węzła wynosi 50, po lewej mamy 0 po prawej mamy 4 węzły
2. Obliczamy wartość dla 10:
   50 - (10-5)4 + (10-5)1 = 50 - 54 +51 = 35
   Więc wartość dla drugiego węzła wynosi 35, po lewej mamy 1 po prawej mamy 3 węzły
3. Obliczamy wartość dla 15:
   35 - (15-10)3 + (15-10)2 = 35 - 53 +52 = 30
   Więc wartość dla drugiego węzła wynosi 30, po lewej mamy 2 po prawej mamy 2 węzły
4. Obliczamy wartość dla 20:
   30 - (20-15)2 + (20-15)3 = 30 - 52 +53 = 35
   Więc wartość dla drugiego węzła wynosi 35, po lewej mamy 3 po prawej mamy 1 węzeł
5. Obliczamy wartość dla 25:
   35 - (25-20)1 + (25-20)4 = 35 - 51 +54 = 50
   Więc wartość dla drugiego węzła wynosi 50, po lewej mamy 4 po prawej mamy 0 węzłów

Oczywiście warto zauważyć że opłaca nam się liczyć tylko do momentu kiedy wartości zaczynają "rosnąć" ;) Więc mamy O(n) + O(n/2)

Zadanie "taksówki" z Olimpiady Informatycznej - temat powinien pójść do kosza a użytkownik dostać bana bo jest to oszustwo.

Hmm faktycznie podane tutaj zadanie wydaje się wykazywać pewne podobieństwo do Taksówek z OI, ale to jest co najwyżej fragment tego zadania. Swoją drogą mam wątpliwości czy autor w ogole poszedł w dobrym kierunku bo przecież Taksówki mogą dojechać do pewnego punktu a potem zawrócić w efekcie autor musiałby podany przeze mnie algorytm odpalać co 1 ruch, a to już daje nam O(n^2) które niekoniecznie przejdzie testy, szczególnie że wydaje mi się że można ten problem rozwiązać liniowo...

Problem, który chcesz rozwiazać to znalezienie medoidu w zbiorze punktów 1D.
Zalozmy, ze mozemy umiescic punkt minimalizujacy sume odleglosci, w dowolnym miejscu na osi. Punkt, ktory minimalizuje sume odleglosci nazywa sie geometryczna medianą (http://en.wikipedia.org/wiki/Geometric_median). Dla przypadku 1D jest to po prostu mediana.
W przypadku gdy liczba danych wejsciowych jest nieparzysta mamy gotowa odpowiedz (bo mediana jest srodkowym elementem posortowanej tablicy).
W przypadku gdy liczba danych wejsciowych jest parzysta wybieramy jeden punkt z dwoch "srodkowych" punktow; ten ktory lepiej minimalizuja sume odleglosci. To zadziała tylko wtedy gdy funkcja, którą minimalizujemy (czyli suma odległości) jest wypukła (ang. convex). A tak się składa, że jest; |xi - m| jest funkcją wypukłą (zmienną jest m) a suma funkcji wypukłych też jest funkcją wypukłą.

W najprostszym przypadku gdy liczymy mediane sortujac dane wejsciowe mamy zlozonosc calego algorytmu O(n log n)
Jak ktos chce lepiej to sa algorytmy szukania mediany w czasie O(n).

PS To zadanie raczej srednio przypomina taksowki.

Ok. W sumie znalazłem algorytm Hoare do liczenia mediany, ale trochę za późno, więc zrobiłem quicksorta i łopatologicznie znalazłem medianę.
@mvt8, żaden zadanie z taksówką. Opanuj się na przyszłość w oskarżeniach.