Predstavíme si dve riešenia: riešenie hrubou silou a optimálne riešenie.

Hrubá sila $$O(n^2)$$

Príklad vieme vyriešiť veľmi jednoducho vyskúšaním všetkých možných začiatkov záchrany: Spočítame, koľko hodín práce by musel Jimi preskočiť, keby začal so záchranou práve v $$i$$-tu hodinu. Zo všetkých $$i$$ vyberieme také, kedy je počet preskočených hodín práce minimálny.

Počet preskočených hodín spočítame tak, že v cykle prejdeme vstupné pole od $$i$$-tej hodiny, pričom si budeme počítať počet prejdených P a H. Ak dosiahneme počet H rovný $$c$$, dosiahli sme potrebný počet hracích hodín a počet P je počet obetovaných pracovných hodín. Stačí teda počet P porovnať s doterajším minimom a ak je menší, našli sme nové minimum.

Keď od hodiny $$i$$ po koniec rozvrhu ostáva menej ako $$c$$ hodín, vypíšeme najmenší počet vynechaných P.

Keďže pre každý začiatok môžeme prejsť až na koniec poľa, časová zložitosť je $$O(n^2)$$.

Optimálne riešenie $$O(n)$$

Môžeme si všimnúť, že v predošlom riešení robíme množstvo práce viackrát. Ak totiž poznáme počet P-čok (označme ho $$p_i$$) v úseku začínajúcom na $$i$$, tak vieme, že počet P-čok v úseku začínajúcom na $$i+1$$ nemusí byť veľmi odlišný. Mohli by sme teda zvýšiť $$i$$ na $$i+1$$ a nezačať počítať P a H od $$i+1$$ ale rovno od $$i + c + p_i$$ (teda odtiaľ, kde sme skončili prechod poľa pre predošlé $$i$$), kým nedosiahneme potrebný počet H-čok.

My budeme postupovať podobne, akurát teraz nebudeme skúšať všetky začiatky, ale prejdeme cez všetky konce.

Budeme sa teda vždy pozerať na časť poľa, ktorá je určená začiatkom a koncom[^1]. Tiež si udržiavame počet P a počet H v tejto časti poľa.

Začneme so začiatkom aj koncom na prvom políčku poľa. V každom kroku cyklu posunieme koniec úseku o jedno políčko ďalej. Kým je počet H v našom úseku väčší alebo rovný $$c$$, posúvame začiatok úseku doprava. Tým dosiahneme najkratší úsek s týmto koncom, ktorý má aspoň $$c$$ H-čok. Keďže je najkratší, má aj minimálny počet P-čok. Počet P-čok porovnáme s medzivýsledkom a zapamätáme si menší.

Po prechode poľom vypíšeme minimum.

Každé políčko poľa sme navštívili raz koncom a najviac raz začiatkom, teda celková časová zložitosť je $$O(n)$$.

#include <iostream>
#include <algorithm>

using namespace std;

int main () {
    int c;
    string vstup;

    cin >> c;
    cin >> vstup;
    int n = vstup.size();

    int zaciatok = 0;
    int H = 0, P = 0;
    int vysledok = n;

    for (int koniec = 0; koniec < n; koniec++) {
        if (vstup[koniec] == 'P') {
            P++;
        } else {
            H++;
        }

        while (H >= c && zaciatok < koniec) {
            vysledok = min(P, vysledok);
            if (vstup[zaciatok] == 'P') {
                P--;
            } else {
                H--;
            }
            zaciatok++;
        }
    }
    cout << vysledok << endl;
    return 0;
}

1. Prístup, ktorým vyriešime túto úlohu sa nazýva “dvaja bežci” – jeden ukazuje na začiatok, druhý na koniec a postupne nimi prejdeme pole.↩