Google Code Gem - Qualification

Так уж получилось что я его пропустил. Поэтому просто порешаю для себя.
Кволификация простая.
Я ее переформулирую чтобы было поинтереснее...

Пусть у нас есть последовательность состоящая из нолей и других различных N чисел.
Например - 0,0,1,0,2,2,0,0,1,3,0,0,0,0,3,0,2
Пусть у нас есть N тригеров. В начальный момент времени какой-то тригер i включен, остальные выключены. Мы сканируем последовательность. Когда встречается номер текущего включенного тригера мы должны этот триггер выключить и включить какой-то другой.
Например - пусть у нас включен в начале 1й триггер, тогда на 3м шаге мы должны выключить 1й и включить какой-то другой.
Задача - минимизировать количество переключений триггеров.

Решение которое пришло мне в голову достаточно простое. Пришлось только повозиться с доказательством его правильности). Решение в виде "жадного" алгоритма. Мы сканируем последовательность отмечая места в который i-й триггер нужно выключить. Когда все триггеры отмечены - последний отмеченный и будет пырвым триггером который мы должны выбрать для включения. Затем помечаем его как включенный и повторяем операцию для оставшейся части последовательность. Если последовательность закончилась - берем 1й попавшийся.

std::vector<int> google_code_gem_intro(std::vector<int>& in,int length)

{

    std::vector<int> res;

    std::vector<int> b;

    for(int i=0;i<length;++i)

        b.push_back(0);

 

    int total=length;

    for(std::vector<int>::iterator tV=in.begin();tV!=in.end();++tV)

    {

        if(!*tV)

            continue;

        if(    b[*tV]==0)

        {

            --total;

            if(!total)

            {

                res.push_back(*tV);

                total = 0;

                for(int i=0;i<length;++i)

                    b[i]=0;

                total=length-1;

            }

            b[*tV]=1;

        }

    }

    if(total)

    {

        for(int i=0;i<length;++i)

        {

            if(!b[i])

            {

                res.push_back(i);

                break;

            }

        }

    }

    return res;

}