Rozwiązanie oparte na maxheap, czas byl nawet dobry, ale okazało się, że “Kolejka monotniczna” wygrała (nie próbowałem tego rozwiązania).
Inna rzecz, ktorą można zauważyć, że przy dodawaniu nowego elementu,
wszystkie poprzednie mniejsze/równe wartości stają się bezużyteczne.
Tak więc użyłem zwykłej tablicy o rozmiarze ‘k’.
Na dodatek początek danych może być w róznym miejscu.
Dane są zawsze posortowane.
Nowa wartość usuwa z tablicy wszystkie mniejsze lub równe elementy, tak więc rozmiar danych jest zawsze optymalny.
Oczywiście, każdy element musi miec jeszcze swój tzw ‘czas dodania’.
Trochę optymalizacji, wyeliminowanie dzielenia, Fast IO -> daje czas naprawdę szybki.
PS: Taka ciekawostka, zastosowałem “bombowy” mechanizm w C dotyczący przechowywania “stringów z liczbami”:
{ /* ten kod jest niezgodny z ANSI-C, generuje tzw. undefined behavior */
char jakis_string [] = "1456789";
char output_buffer [100];
long value;
/* zapamietaj zawartosc stringa - nie potrzeba kopiowac bajt po bajcie */
value = *(long *)jakis_string;
/* wypisz string do bufora wyjściowego */
/* tu znowu - brak potrzeby kopiowania bajtow */
*(long *)output_buffer = value;
}
Ten mechanizm jest “bombowy”, bo to jest kompletnie złe rozwiązanie, jest to niezgodne z ANSI-C,
czasami zadziała, czasami nie (long nie musi mieć aż 8 bajtów, niewyalignowany dostęp do pamięci itd.).
!!! Nie wolno tak pisać kodu !!!
Przydaje się to wtedy, gdy walczymy o czas, w tym zadaniu dzięki takiemu podejściu uzyskałem dodatkowo tylko 0.02s.