1144. Autobus [MWPZ06C]

Zadanie:
https://pl.spoj.com/problems/MWPZ06C

Skrócony opis problemu:

Do $n$-osobowego autobusu wsiada $m$ osób. Jest 1 rząd miejsc siedzących. Pierwsza osoba siada na miejscu $x$. Kolejne osoby siadają wg następujących zasad:

• kolejna osoba wybiera miejsce, którego odległość do najbliższego zajętego miejsca jest jak największa
• jeżeli miejsc, na których może usiąść naukowiec (zgodnie z poprzednim punktem) jest więcej to wybiera on takie, które jest najbliżej wejścia (tj. z najmniejszym numerkiem)
• naukowcy nie zwracają uwagi na fakt istnienia kierowcy w autobusie

Dla $y$ wybranych osób należy podać ich miejsca (numerowane od 1 do $n$).

Rozwiązanie naiwne:

Oczywiście można dla każdej kolejnej osoby sprawdzać odległość między każdą parą kolejnych osób, wybrać najdalej siedzących sąsiadów, a następnie posadzić osobę między nimi.

Złożoność: $O(m \cdot n)$, gdyż dla każdej wsiadającej osoby będziemy przeglądać pesymistycznie $n$ miejsc. Dla maksymalnych danych (gdzie $m = n$) złożoność to $O(n^2)$.

Rozwiązanie sprytne:

Skoro złożoność rozwiązania naiwnego to $O(n^2)$, to możemy się domyślić, że wzorcowa złożoność to $O(n \log n)$, $O(n \log \log n)$ lub $O(n)$. W ostatnim przypadku musielibyśmy dla każdej osoby wykonywać stałą liczbę operacji, a więc od razu wiedzieć gdzie ma usiąść. Możemy wyczuć, że jest to zbyt trudne, a może nawet niemożliwe. Tak więc pozostały nam 2 złożoności z logarytmami. Sugeruje to, że albo skorzystamy z wyszukiwania binarnego, albo użyjemy jakiejś struktury, na której operacje mają złożoność $O(\log n)$. W przypadku wyszukiwania binarnego powinniśmy mieć jakieś posortowane lub uporządkowane dane, a w naszym przypadku ludzie siadają jak najdalej od siebie, więc mamy sporo luk w autobusie. Wyszukiwanie binarne niezbyt tutaj więc pasuje. Pozostała struktura z logarytmicznym dostępem.

Weźmy sobie zatem seta i spróbujmy wykorzystać go do rozwiązania naszego zadania. Pierwsza osoba siada na miejscu nr $x$. Co możemy wrzucić do seta, żeby zwrócił nam największy pusty ciąg miejsc? Jeśli wrzucimy to $x$, to jedyne co nam zwróci set to może być $x$. Jeśli zrobimy odwrotnie i wrzucimy liczby od 1 do $x-1$ i od $x+1$ do $n$ to też nic nam nie da. Co możemy zatem zrobić?

Ano zamiast wrzucać liczby możemy wrzucać przedziały pustych miejsc. Na początku mamy 1 zajęte miejsce. Wrzucamy zatem przedziały $\left<1; x-1\right>$ oraz $\left<x+1; n\right>$. Następnie w pętli dla każdej kolejnej osoby pobieramy najlepszy przedział (najdłuższy i najbliższy początkowi autobusu), usuwamy go i dzielimy na 2 równe przedziały. Je następnie z powrotem wrzucamy do seta. Ale chwila, chwila! Wiadomo, że druga osoba usiądzie na jednym z dwóch końców autobusu. A my zawsze usadawiamy kolejne osoby pośrodku naszego przedziału. Mamy więc błąd. Np. dla danych $n=10$ oraz $x=7$, druga osoba powinna usiąść na miejscu 1, a usiądzie na miejscu $\left\lfloor\frac{1+6}{2}\right\rfloor = 3$. Co możemy z tym zrobić? Ano musimy po prostu zmodyfikować pierwsze przedziały tak, żeby ich środki znajdowały się w punktach 1 oraz $n$. Czyli dla poprzedniego testu nie wrzucimy do seta przedziałów $\left<1; 6\right>$ oraz $\left<8; 10\right>$, ale $\left<-4; 6\right>$ oraz $\left<8; 12\right>$, bo wtedy mamy środki w miejscach 1 i 10.

Pozostało ogarnąć przypadki szczególne, w których mielibyśmy śmieci w secie. Takim przypadkiem byłoby np. gdybyśmy podzielili wspomniany wcześniej przedział $\left<-4; 6\right>$ na 2 części i wrzucili przedział $\left<-4; 0\right>$ do seta. Wystarczy więc dodać ifa, że jeśli któraś z granic przedziału ma wyjść poza granicę miejsc w autobusie, to jej nie wrzucamy do seta. Drugim i ostatnim przypadkiem jest przedział pusty.

Tutaj jeszcze pozwolę sobie coś zauważyć. Musimy zaimplementować funkcję/strukturę/klasę, która będzie nam porównywać nasze przedziały. W owej funkcji musimy uważać, żeby nie porównywać długości przedziałów, ale ich połowy. Dlaczego? Ano dlatego, że jeśli mamy sobie przedział o długości 1 i inny o długości 2, to znaczy, że w tym drugim i tak będziemy siedzieć koło jakiejś osoby. W pierwszym przypadku usiądziemy pomiędzy 2 osobami, a w drugim będziemy mieli 1 miejsce wolne koło nas, jednak odległość od najbliższej osoby jest nadal 1. Długości 1 i 2 musimy zatem rozpatrywać jako równe i wybierać ten bliższy kierowcy. Moim zdaniem nie powinno tak być, bo bardziej naturalna jest minimalizacja osób siedzących koło nas, ale z drugiej strony w tym przypadku zadanie jest bardziej podchwytliwe. Tak czy inaczej, pamiętajcie o tym.

Optymalizacja: Zamiast seta możemy użyć szybszej struktury danych (jednak asymptotycznie równie szybkiej), którą jest priority_queue. Kiedy używać jej, a kiedy seta? Jeśli potrzebujemy dostępu jedynie do jednej najlepszej (najmniejszej lub największej) wartości, to powinniśmy skorzystać z priority_queue. W tym przypadku potrzebujemy jedynie najszerszego przedziału, więc jak najbardziej powinniśmy wybrać kolejkę priorytetową z STLa. Gdybyśmy jednak chcieli pobrać/usunąć wartość ze środka struktury - wybieramy seta.

Złożoność: $O(m \log n)$, gdyż dla każdej osoby wykonujemy jedynie do 3 operacji na naszej strukturze w czasie logarytmicznym względem ilości miejsc w autobusie. Dla maksymalnych testów złożoność to $O(n \log n)$.

Algorytm:

Uwaga: W poniższym kodzie przedziały mają niedomknięte końce. Czyli końce przedziału oznaczają zajęte miejsca, a nie puste. Łatwiej było mi tak zaimplementować.

struct comp
{
        bool operator() (const pair<int,int> &a, const pair<int,int> &b) const
        {
                if(a.second-a.first>>1 == b.second-b.first>>1) // jeśli połowy długości przedziałów są takie same to wybierz przedział bliższy kierowcy
                        return a.first > b.first;
                return a.second-a.first < b.second-b.first; // w przeciwnym wypadku wybierz przedział o większej długości
        }
};
int main()
{
        int t, n, m, x, y, tab[20009], place[20009];
        pair<int, int> p;
        priority_queue<pair<int,int>, vector< pair<int,int> >, comp> q; // kolejka priorytetowa z własnym porównywaniem

        get(n, m, x, y);
        for(int i = 0; i < y; ++i)
                get(tab[i]);
        place[1] = x; // pierwsza osoba siada na miejscu x
        if(x > 1) // jeśli pierwsza osoba nie siada na początku
                q.push(make_pair(2-x, x)); // wrzuć do kolejki przedział, w którym środkiem jest miejsce 1
        if(x < n) // jeśli pierwsza osoba nie siada na końcu
                q.push(make_pair(x, 2*n-x)); // wrzuć do kolejki przedział, w którym środkiem jest miejsce n
        for(int i = 2; i <= tab[y-1]; ++i) // dla każdej osoby do ostatniej, o którą nas pytają
        {
                p = q.top(); q.pop(); // bierzemy najlepszy przedział z kolejki i go usuwamy
                place[i] = p.first+p.second>>1; // usadawiamy i-tą osobę na środku przedziału
                if((p.first+p.second)/2-p.first > 1 && p.first > 0) // jeśli przedział nie jest pusty i nie jest poza przedziałem miejsc autobusu
                        q.push(make_pair(p.first, p.first+p.second>>1)); // wrzuć go do kolejki
                if(p.second-(p.first+p.second)/2 > 1 && p.second < n+1) // jak wyżej
                        q.push(make_pair(p.first+p.second>>1, p.second));
        }
        for(int i = 0; i < y; ++i) // dla każdej interesującej nas osoby wypisz, gdzie siedzi
                print(place[tab[i]]);
}