4. Stovky programátorov vzorové riešenie

10
158
182
112
92
52
201
193
167
177
167

158
158
158
112
112
112
158
158
167
167

10
83
36
16
58
65
80
52
83
73
71

83
36
36
36
58
58
58
58
65
65

V tejto úlohe potrebujeme udrživiať čísla tak trochu usporiadané. To sa dá robiť pomocou rôznych pomerne zložitých dátových štruktúr. My si ukážeme riešenie, ktoré využíva iba haldu. To ako, prečo, ako rýchlo… halda funguje bolo v študíjnom texte o Halde.

Riešenie s jednou haldou

Vieme že táto úloha má byť o halde. Skúsime sa teda zamyslieť ako by sme vedeli haldu využiť. Vlastnosť haldy je, že vieme jednoducho nájsť ktorý prvok je najväčší (prípadne najmenší). O ostatných prvkov však nevieme skoro nič povedať. Jedno z riešení, by teda mohlo byť že si budeme skúseností programátorov držať v halde. Potom v každom kroku z našej haldy vyberieme polovicu prvkov, zistíme hodnotu mediánu, a následne všetky prvky naspať vrátime. Takéto riešenie je však veľmi pomalé.

Optimalizácia predošlého riešenia

Môžeme si všimnúť, že v predošlom riešení robíme veľa “roboty” zbytočne. Na konci každého kroku najprv polovicu prkov vrátime len na to, aby sme ich neskôr skoro všetky znovu z haldy vybrali. Toto je samozrejme zbytočné. Nechajme teda polovicu prvkov stále vybranú.

Máme teda prvky rozdelené na dve rovnako veľké skupiny, v jednej sú prvky väčšie ako medián, v druhej prvky menšie alebo rovné ako medián. Teraz vieme jednoducho vypísať hodnotu mediánu, je to totiž najväčší prvok z druhej skupiny. Ako si však vieme udržiavať tieto skupiny, keď budú pribúdať nový programátori?

Keď nám príde nové číslo(nový programátor) najprv zistíme do ktorej skupiny by malo patriť. Tak ho tam teda pridáme. Teraz by mohol nastať problém, a to, že v tejto skupine je teraz veľa prvkov. Vtedy treba jeden prvok presunúť do druhej skupiny (môžete si premyslieť, prečo určite stačí presunúť jeden prvok). Prvok, ktorý musíme presunúť je ten najväčší/najmenší z danej skupiny, aby stále platilo, že skupiny sú rozdelené podľa veľkosti. Keďže z času na čas potrebujeme zistiť, a vybrať najväčší resp. najmenší prvok, budeme si naše skupiny ukladať ako haldy.

Zhrnutie

Budeme mať teda dve haldy, jednu maximovú a jednu minimovú. V maximovej bude polovica(zaokrúhlené nahor) všetkých prvkov, a budú to tie menšie. V minimovej zase budú tie väčšie prvky. Vždy keď dá svoju ponuku nový programátor najprv ho pridáme a upravíme skupiny, a potom jednoducho nájdeme vhodného programátora.

Časová zložitosť

V každom kroku, teda vždy keď pridávame nejakého programátora spravíme niekoľko operácií s haldami. Každá táto operácia nám zaberie najviac \(O(log n)\), a teda keďže týchto krokov spravíme \(n\), celková zložitosť bude \(O(nlog n)\).

Implementácia

V kóde využijeme to, že haldu niekto pred nami už naprogramoval. V c++ využijeme priority_queue.

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    int n;
    cin >> n;

    priority_queue<int, vector<int>, greater<int>> minimova;
    priority_queue<int, vector<int>, less<int>> maximova;

    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;

        if(maximova.size() == 0 || x <= maximova.top())
        {
            maximova.push(x);
        }
        else minimova.push(x);

        if(maximova.size() < minimova.size())
        {
            maximova.push(minimova.top());
            minimova.pop();
        }
        else if(maximova.size() >= minimova.size() + 2)
        {
            minimova.push(maximova.top());
            maximova.pop();
        }

        cout << maximova.top() << endl;
    } 
    
    return 0;
}