2. Zrýchlenie parkoviska vzorové riešenie

3 7
4
9039
103
19
4
103
47

0
1
2
plne
0
2
2

Pre každý riadok vstupu (ŠPZ auta) riešime jednu z dvoch úloh: parkovanie (nájdi voľné miesto) alebo vyparkovanie (nájdi miesto, na ktorom auto bolo).

Obe sa dajú jednoducho vyriešiť napríklad takto: parkovisko si budeme pamätať ako pole, kde parkovisko[i] bude obsahovať buď ŠPZ auta, ktoré stojí na mieste \(i\), alebo špeciálnu hodnotu, ak je miesto prázdne. Na zodpovedanie otázky prezeráme parkovisko miesto po mieste, kým nenájdeme dané auto a potom ho vyparkujeme. Ak auto nenájdeme, vyhľadáme mu voľné miesto. Toto riešenie je ale zjavne veľmi pomalé, pretože pre každé auto musíme prehľadať prinajhoršom celé parkovisko. Časová zložitosť takéhoto riešenia je potom \(O(mn)\).

Malým, ale v niektorých prípadoch významným, zlepšením jednoduchého riešenia je nezačínať hľadanie prázdneho miesta vždy odznova. Budeme ho hľadať od miesta, kam zaparkovalo posledné auto. Týmto zrýchlime hľadanie miesta, samozrejme, len pokiaľ sa nezaplní posledné miesto parkoviska. Zvyšok výpočtu sa nespomalí, a preto je toto riešenie lepšie, hlavne ak prichádzajúcich áut je málo a parkovisko veľké.

Toto ale nestačí. Ak by po zaplnení parkoviska stále prichádzali autá na miesta s číslami \(m\) a \(m/2\), pre každú otázku zo vstupu prehľadávame stále \(O(m)\) miest. Chceme teda nájsť buď voľné miesto, alebo miesto, kde je auto zaparkované bez nutnosti prehľadať parkovisko. Na to si ukážeme dva zlepšováky:

Keď auto zaparkuje, jeho miesto sa už meniť nebude. Preto môžeme vyparkovanie zrýchliť na konštantný počet operácií tým, že pre každé zaparkované auto si budeme pamätať miesto, na ktorom stojí a pri vyparkovaní ho uvoľníme. Toto dosiahneme napríklad tým, že budeme mať pole a v ňom políčko pre každú možnú ŠPZ. Keď auto nie je zaparkované, pamätáme si v tomto políčku hodnotu \(-1\) (alebo inú, ktorá nie je platné číslo parkovacieho miesta). Ak príde auto zaparkovať a nájdeme mu miesto, do tohto políčka uložíme číslo miesta, kam zaparkovalo. Keď bude odchádzať, stačí sa pozrieť na toto políčko a hneď vieme, ktoré miesto treba uvoľniť.

Druhým zlepšovákom chceme zrýchliť hľadanie voľného miesta. Uvedomte si, že je nám jedno, na ktoré voľné miesto prichádzajúce auto zaparkujeme. Dôležité je len, aby sme to robili rýchlo. Pamätajme si preto všetky voľné miesta v jednom poli. Na začiatku toto pole obsahuje všetky čísla od 1 po \(m\).

Ak príde auto a chceme mu priradiť voľné miesto, pozrieme sa jednoducho na posledné miesto tohto poľa. Tam sa nachádza nejaké voľné miesto, ktoré mu priradíme. V tomto momente však toto miesto už nie je voľné – potrebovali by sme ho z tohto poľa vyškrtnúť a pole skrátiť. To vieme robiť rýchlo buď pomocou dynamických polí¹ alebo len použijeme jednu premennú posledneVolne, ktorá nám hovorí, koľko voľných parkovacích miest máme. Namiesto skracovania poľa nám preto bude stačiť zmenšiť túto premennú o 1.

Ak auto odchádza, vyššie uvedeným spôsobom zistíme, ktoré miesto uvoľnilo. Toto voľné miesto si zapíšeme do nášho poľa voľných miest, a to tak, že zväčšíme premennú posledneVolne a do poľa si na toto miesto zapíšeme uvoľnené parkovacie miesto.

Takto máme celý čas k dispozícii zoznam voľných miest a nemusíme sa preto pozerať na všetky ostatné (aj obsadené) parkovacie miesta. Dátová štruktúra, do ktorej vieme na koniec vkladať a z jej konca vyberať prvky sa často používa a tak dostala aj názov – zásobník, po anglicky stack. V predošlých odsekoch sme si vlastne popísali, ako taký zásobník naprogramovať.

Keď použijeme oba zlepšováky, na parkovanie alebo vyparkovanie jedného auta potrebujeme iba konštantný počet operácií. Obslúžiť \(n\) príchodov alebo odchodov bude teda trvať \(O(n)\) operácií.

V pamäti si musíme držať voľné miesta, ktorých je nanajvýš \(m\) a parkovacie miesta pre všetky ŠPZky². Napriek tomu, že v našej úlohe sú tieto hodnoty len do \(1\,000\,000\), nie je slušné povedať, že pamäťová zložitosť je konštantná. Omnoho viac prezradíme, ak si označíme maximálnu hodnotu ŠPZ ako napríklad \(S\) a potom môžeme povedať, že pamäťová zložitosť algoritmu je \(O(m + S)\).

#include <iostream>

#define MAXSPZ 1000042

using namespace std;

int parkovacie_miesto[MAXSPZ]; // -1 ak auto s danou SPZ nie je na parkovisku

int main() {
    int n, m;

    cin >> m >> n;
    int volne[m];

    //inicializujeme polia
    for (int i = 0; i < MAXSPZ; i++) {
        parkovacie_miesto[i] = -1;
    }
    int posledneVolne = m-1;
    for (int i = 0; i < m; i++) {
        volne[i] = i;
    }

    for (int i = 0; i < n; i++) {
        int spz;
        cin >> spz;
        if (parkovacie_miesto[spz] != -1) { // ak auto je uz zaparkovanie
            int praveUvolnene = parkovacie_miesto[spz];
            parkovacie_miesto[spz] = -1;
            posledneVolne++;
            volne[posledneVolne] = praveUvolnene;
            cout << praveUvolnene << endl;
        } else {
            if (posledneVolne == -1) {      // ak chcem parkovat ale nie je volne miesto
                cout << "plne" << endl;
            } else {                        // ak parkujem a mam kam 
                int praveZaplnene = volne[posledneVolne];
                posledneVolne--;
                parkovacie_miesto[spz] = praveZaplnene;
                cout << praveZaplnene << endl;
            }
        }
    }
    return 0;
}

m, n = [int(x) for x in input().split(' ')]

parkovacie_miesto = [-1] * 1000047     # -1 ak auto s danou SPZ nie je na parkovisku
volne = [x for x in range(0, m)]

for i in range(n):
    spz = int(input())
    if (parkovacie_miesto[spz] != -1): # ak auto je uz zaparkovane
        miesto = parkovacie_miesto[spz]
        volne.append(miesto)
        parkovacie_miesto[spz] = -1
        print(miesto)
    else:
        if (len(volne) == 0):          # ak chcem parkovat ale nie je volne
            print('plne')
        else:                          # ak chcem parkovat a mam kam
            miesto = volne.pop()
            parkovacie_miesto[spz] = miesto
            print(miesto)