1890. Mário

Olá meus amigos nerds, hoje iremos ajudar nosso amigo Mário a resolver seus problemas. Não me pergunte, que Mário? Pois, não resistirei fazer aquela piadinha infame, ainda mais que o problema de hoje fala de armários.

O problema 1890. Mário nos pede para ajudar nosso amigo Mário a organizar seus armários, de modo a atender de melhor seus clientes. Mais especificamente, dado um conjunto de armários livres e numerados (e com rodinhas) nos é pedido que calcule qual é o menor número de movimentações de armários que deve ser feito para que esses armários livres sejam dispostos de modo a haver n armários livres em sequência.

Solução

Esse é um problema interessante, pois a princípio ele parece bem difícil, mas na realidade é fácil. Observe, inicialmente, que o número de movimentos (trocas) necessários para dispor n armários vazios em sequência é menor que n (pelo menos um armário vazio já estará no lugar). Observe ainda, que a sequência de armários vazios necessariamente começará em um dos L armários (obvio). Se decidirmos começar nossa sequência de armários a partir do armário i, teremos que trocar de posição todos os armários ocupados a partir de i até (i+n). Assim, se contarmos quantos armários ocupados existem a partir de cada i em L e escolhermos o menor desses números teremos nossa resposta. Essa  é precisamente a ideia do algoritmo abaixo, onde contamos o número de armários desocupados (que é complementar ao número de armários ocupados) uma vez que essa é a informação que a entrada do problema nos fornece.

maiorNumArmariosDesocupados = 0

for i in (L-n) //L-n é a última posição em que eu posso iniciar uma sequência de n armários

    Seja x o número de armários desocupados existentes dentro da janela [i, i+n]
    if x > maiorNumArmariosDesocupados
        maiorNumArmariosDesocupados = x

numTrocas = n - maiorNumArmariosDesocupados

Implementação

Observe que em minha implementação eu armazeno apenas as posições dos armários vazios. Isso me permite otimizar um pouco o meu for.