Długa Taśma - Ilocamp 2011

Rozwiązuję zadanie Długa Taśma z grupy początkującej z obozu Ilocamp 2011. http://main.edu.pl/pl/archive/ilocamp/2011/dlu

Doszedłem jedynie do tego, że aby średnia arytmetyczna (a_p + a_p+1 + ... + a_k)/(k - p + 1) była jak najmniejsza, muszę zminimalizować licznik oraz możliwie zmaksymalizować mianownik. Nasuwa to rozwiązanie w złożoności O(n^2), gdzie liczę sumy prefiksowe ciągu, a następnie sprawdzam każdą możliwą średnią. Niestety, takie rozwiązanie jest stanowczo za wolne i muszę wymyślić coś co będzie działać w czasie O(n log n) lub O(n). Bardzo proszę o waszą pomoc.

Weź liczby x i y, a następnie zastanów się, kiedy średnia arytmetyczna liczb x i y będzie mniejsza od średniej arytmetycznej liczby x lub średniej arytmetycznej liczby y.

Masz na myśli, kiedy zachodzi nierówność (x+y)/2 < x? Wtedy gdy x > y. Ale nie widzę związku z zadaniem.

No to rozpatrzmy kilka przypadków:
Przypadek 1: x < y. Wtedy:
(x + y) / 2 > (x + x) / 2 = x
oraz
(x + y) / 2 < (y + y) / 2 = y
Czyli średnia arytmetyczna liczb x oraz y jest pomiędzy tymi liczbami (żadnego zaskoczenia).

Przypadek 2: x > y. Wtedy jest to samo, co w przypadku 1.

Przypadek 3: x = y. Wtedy:
(x + y) / 2 = (2x) / 2 = x
(x + y) / 2 = (2y) / 2 = y
Czyli średnia arytmetyczna obu liczb jest równa każdej z tych liczb.

Teraz pytanie: czy opłaca się brać kilka liczb, jeżeli chcemy zminimalizować średnią arytmetyczną?

Hm... chyba nie opłaci się. Jeżeli te liczby będą różne to średnia będzie należeć do przedziału (min(a₁, a₂,...a_n), max(a₁, a₂,...a_n)), a im więcej ich weźmiemy tym większy może być max() z tych liczb. Zatem wystarczy sprawdzić tylko średnie arytmetyczne sąsiednich par liczb oraz pojedyncze liczby. Mam rację?

Edit: Nie, jednak wystarczy sprawdzić tylko pojedyncze liczby. Jednym słowem - rozwiązaniem zadania jest min() ze wszystkich liczb. Dzięki za pomoc :D

No to zastanówmy się inaczej.
Weź dowolną liczbę z ciągu, nazwij ją x i spróbuj rozszerzyć podciąg w prawą stronę o liczbę y. Początkowo średnia arytmetyczna wynosiła x (bo tylko jedna liczba x tworzyła podciąg), teraz średnia arytmetyczna wynosi (x+y)/2. I teraz:

1. Jeżeli y było większe od x, to średnia arytmetyczna wzrosła. Wobec tego rozszerzenie podciągu o liczbę y się nie opłaca.
2. Jeżeli y było mniejsze od x, to średnia arytmetyczna zmalała. Ale jednocześnie średnia (x+y)/2 jest większa, niż liczba y, więc zamiast rozszerzać podciąg lepiej pozbyć się x i wziąć liczbę y.
   A jeżeli ciągle nic Ci to nie mówi, to weź kilka ciągów dwu-, trzy- i cztero-elementowych, a następnie sprawdź, jaka jest odpowiedź dla każdego z nich.