🚀 go-pugleaf

Dnia Wed, 16 Nov 2005 16:39:56 +0100, Piotr Dembiński skrobie:
> > Jaka jest _minimalna_ liczba porownan ? 

> 10 mln minus pięć plus to, co potrzebne by stwierdzić, że pierwsze
> pięć liczb w tablicy tworzy potrzebny kopiec.

I co zrobisz jak już te liczby porównasz?

> > Wartosc dokladna poprosze, bez oszacowan :-)

> Dokładnie to będzie 10^6 - 5 + 4.

> > [Uwaga - dowod jest duzo trudniejszy niz samo rozwiazanie]

> Trzeba przynajmniej raz porównać wybraną liczbę z pozostałymi.

Przypominam, że co do zbioru liczb nie ma żadnych założeń. Również co do tego,
czy liczby się powtarzają.

Zatem jeśli masz w zbiorniku np. { 2 3 5 5 6 10 10 10 10 9 10 7 7 }, to wtedy
kolejka 5 liczb po zakończeniu przetwarzania musi zawierać { 10 10 10 10 10 }.

Czyli najprościej to albo wziąć pierwsze pięć liczb "jak leci", a potem każdą
wsadzać do zbioru, usuwając z niej najmniejszy element. Operacja wsadzania do
zbioru jest jedyną, w której stosuje się jakiekolwiek porównanie. W najlepszym
razie będzie się okazywało, że wsadzany element jest większy od największego,
więc po jednym porównaniu wyląduje na szczycie.

-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethourhs(O)wp.pl>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"