Nie musisz mieć wektora dla każdego renifera. Możesz mieć jeden wektor na wszystkie renifery, który będzie przechowywał informację ile jest prezentów we wszystkich wagonikach o danym numerze(niech nazywa się renifery). I będzie potrzebny jeszcze drugi wektor, w którym przechowamy informację o liczebności elementów tego pierwszego(liczebność).
Np. jeśli n = 3, k = 3 i w wagonikach o numerach 1 jest 2 prezenty, w wagonikach o numerach 2 jest 1 prezent i w wagonikach o numerach 3 też jest 1 prezent, to wektor renifery={2,1,1}, a wektor liczebność={0, 2, 1}, bo nie ma w wektorze renifery liczb 0, jest 2 jedynki i 1 dwójka.
Mając te 2 wektory możemy łatwo obsłużyć dodanie nowego prezentu. jeśli widzimy, że trzeba dodać prezent x to wykonujemy następujące operacje:
int tmp = renifery[x] // zapisujemy ile tu juz było prezentów
renifery[x]++; // dorzucamy prezent;
// w wektorze renifery tak jakby usuwamy jedno tmp i dodajemy tmp+1 w jego miejsce
// odpowiednio aktualizujemy liczebność
liczebność[tmp]--;
liczebność[tmp+1]++;
Co robimy jeśli jakiś renifer odjedzie? Nic. W tablicy renifery będzie też informacja o prezentach, które już opuściły warsztat. Jeśli w wektorze renifery najmniejsza wartość to np. 3, to wiemy, że na każdy adres mamy co najmniej 3 prezenty, więc wiemy, że 3 renifery mogły zostać załadowane i odjechać. Więc gdy w którymś momencie różnica wartości minimalnej i maksymalnej przekroczy k, to możemy odpowiedzieć, że nie da się dostarczyć prezentów, w przeciwnym przypadku da się to zrobić. Teraz, żeby szybko znaleźć minimum i maksimum w reniferach użyjemy wektora liczebność. Minimum w wektorze renifery, to najmniejszy indeks w liczebności, poz którym jest wartość różna od zera.
Np. dla wektora liczebność={0,0,0,0,1,0,2,3,4,0,1,0,0,0}, wiemy, że minimum w wektorze renifery to 4 a maksimum to 10 (liczymy od 0). Ale przeszukiwanie wektora liczebność za każdym razem też jest bardzo wolne. Ale w wektorze liczebność zawsze "przenosimy" jedną liczbę o 1 w górę, (jak w kodzie wyżej). Więc minimum i maksimum również może zmienić się tylko o 1. Możemy zapisać sobie w 2 dodatkowych zmiennych aktualne minimum i maksimum. Gdy liczebność[minimum] spadnie do 0 robimy minimum++, a gdy liczebność[maksimum+1] zwiększy się z 0 do 1 to również maksimum++.
Teraz gdy maksimum - minimum > k to wypisujemy, że się nie da, a gdy dojdziemy do końca to ok.
Rozwiązanie jest już dobre, ale jest jeszcze jeden haczyk. "wektor" liczebność jak go nazywałem musi mieć wielkość co najmniej 10^7 bo tyle może być prezentów jednego typu. Czyli na razie algorytm nie daje żadnego zysku pamięci. Ale można zauważyć, że liczebność zawsze jest postaci {dużo zer ... 0, jakieś liczby , 0 ... dużo zer} i długość fragmentu "jakieś liczby" jest <= k które jest co najwyżej 100. Więc można zasymulować ten wektor na bardzo małej tablicy lub łatwiej na std::map usuwając miejsca, gdzie mamy 0. Teraz pamięć powinna być ok