17208. Bajtek w przedszkolu [AL_12_05]

Zadanie:
http://spoj.com/ALGOLIGA/problems/AL_12_05
http://pl.spoj.com/ALGOLIGA/problems/AL_12_05

Skrócony opis problemu:

Dla ciągu $n$ liter 'C' i $n$ liter 'K' wypisać najmniejszą sumę kosztów połączeń między literami 'C' z literami 'K', gdzie koszt połączenia to odległość między tymi literami. Np. koszt połączenia dla CK to 1, dla CXK to 2, dla CXXK to 3, itd. Dla CKCK wynik to 2, gdyż łączymy pierwsze C z pierwszym K i ostatnie C z ostatnim K.

Algorytm naiwny:

Dla pierwszego C sprawdzamy wszystkie $n$ K. Dla drugiego C zostaje do sprawdzenia jedynie $n-1$ K. Dla trzeciego $n-2$. Sprawdzamy tak wszystkie możliwe kombinacje.

Złożoność: $O(n!)$.

Algorytm sprytny:

Możemy rozwiązać problem zachłannie. Każde C będziemy parować z najbliższym, niezużytym jeszcze K. Albo na odwrót. Np.:

Trzeba się jednak zastanowić czy nie lepiej sparować wszystkie te KC, które są obok siebie. Każde doda nam bowiem jedynie +1 do wyniku. Załóżmy, że sparujemy pierwsze podsłowo KC i zmienimy sumę na 1. Dla pierwszego K najbliższe C jest odległe o 5. Sumą obu tych operacji będzie wtedy 6. A co by się stało gdybyśmy połączyli je na odwrót? Otrzymalibyśmy 3+3, a więc również 6. Czemu tak się dzieje? Otóż pierwsze K musi tak czy inaczej przejść 3 "kroki" to pierwszego C. Jeśli zajmiemy owe C, to dla pierwszego K wykonamy dodatkowe 2 kroki. A więc tracimy 2 kroki. Jednak jeśli pierwsze K sparujemy z pierwszym C, to trzecie K będzie musiało wykonać również dodatkowe 2 kroki do kolejnego C. Możemy wyobrazić to sobie jeszcze inaczej. Idziemy z pierwszego K do trzeciego K wykonując 2 kroki. Teraz jesteśmy w miejscu trzeciego K i mamy 2 litery K do sparowania. Nie obchodzi nas które K pójdzie do którego C (oczywiście z tych dwóch najbliższych - wybranie dwóch najdalszych C nie miałoby sensu). I tak otrzymamy 1+3, a po dodaniu poprzednich 2 kroków otrzymamy 6.

Należy przemyśleć typ zmiennej, w której będziemy przechowywać wynik. Najgorszym przypadkiem jest takie rozłożenie, w którym C i K się nie przeplatają, tylko występują w dwóch skupiskach. Np. CCCKKK albo KKKKCCCC. Wynik to wtedy $n^2$, a dla $n=10^6$ przekroczy on unsigned inta.

Złożoność: $O(n)$. Możemy liniowo zapisać sobie na jednym stosie wystąpienia C, na drugim wystąpienia K, a następnie parować je zdejmując po jednej wartości ze stosów.

Algorytm:

int main()
{
    int n, i, a, b, c[MAX_N], k[MAX_N];
    char tab[MAX_N*2];
    long long x;

    while(get(n))
    {
        get(tab);
        for(x = a = b = i = 0; i < 2*n; ++i)
            if(tab[i] == 'C')
                c[a++] = i;
            else if(tab[i] == 'K')
                k[b++] = i;
        for(i = 0; i < n; ++i)
            x += abs(c[i]-k[i]);
        print(x);
    }
}