Próbuję zrobić to zadanie: http://pl.spoj.pl/problems/CANTEEN/ i zastanawiam się w jaki sposób najszybciej je zrobić? Niby je zrobiłem, ale przekraczam limit czasu. Przypuszczalnie może być to winą tego, że mam wiele klas potworzonych i w sumie sporo jest tworzonych obiektów przez to, co zapewne zwalnia algorytm. Chodzi mi więc o jakiś ogólny zarys, ideę jak to zadanie można szybciej zrobić?
0
1
Kolejka priorytetowa?
0
To na pewno zastosuję, może jeszcze jakieś pomysły?
1
Chyba dwie kolejki powinny wystarczyć,pierwsza dla osób które mają przyjść, lub jedzą (uporządkowana po czasie chęci dostępu do stołówki), druga dla osób oczekujących (porządek po starszeństwie, następnie po czasie przyjścia), . W danym kroku, przenosisz wszystkie osoby z pierwszej do drugiej, które mają czas chęci dostępu równy teraźniejszemu czasowi, następnie pobierasz najbardziej uprzywilejowaną osobę z drugiej i jeżeli ma zjeść jeszcze drugie dodajesz ją do kolejki pierwszej ze zaktualizowanym czasem. Jeżeli są osoby w drugiej kolejce, to zwiększasz czas o jeden i przechodzisz do początku kroku. W innym przypadku zwiększasz czas do czasu chęci skorzystania górnej osoby z pierwszej kolejki.
Trochę pewnie będziesz musiał zmienić ten algorytm, bo chyba wszystkich warunków nie uwzględniłem (np. oczekiwanie w drzwiach do stołówki, nie wiem czy wtedy 3 kolejki nie musisz dodać, do drzwi), ale w tym algorytmie złożoność nie powinna przekroczyć O(nlogn), czyli nadaje się na 50k elementów.
Co do TLE, to zastanów się, czy twój algorytm działa w O(nlogn) gdy wszyscy przyszli w tym samym czasie i jedzą zupę tak samo szybko.
Edit 2: Widzę, że jest osobna kolejka po zupę i drugie, czyli możliwe, że potrzebujesz 4 kolejek.
0
Dzięki, pokombinuję z tym :)