Solução por Samyra Almeida
Para resolver esse problema é necessário conhecer duas técnicas de programação, a primeira chama-se soma de prefixos e a segunda busca binária.
Bem, iremos realizar uma soma de prefixos da seguinte forma, sendo $$pref[i] =$$ a quantidade de zeros da posição $$1$$ até a $$i$$-ésima posição:
- Se $$v[i] = 0$$, fazemos: $$pref[i] = pref[i-1] + 1$$.
- Caso contrário, fazemos: $$pref[i] = pref[i-1]$$.
Com isso, note que o vetor $$pref$$ esta ordenado, pois dado qualquer posição $$i$$ de $$pref$$, podemos garantir que $$pref[i]$$ ou é igual ao $$pref[i-1]$$, ou uma unidade maior.
Sabendo disso, agora vamos pensar em como utilizar a busca binária.
Então, dada uma posição $$i$$ qualquer, vamos mudar os $$k$$ primeiros zeros que estão de $$i$$ até $$N$$.
Para isso, vamos analisar dois casos:
- Se $$v[i] = 0$$, mudamos o cara $$i$$, agora temos $$k-1$$ zeros para mudar, para isso note que basta usarmos a busca binária para procurar a ultima posição $$x$$, no vetor $$pref$$, que possui valor igual a $$pref[i] + k – 1$$, ou seja, a posição do cara que possui $$k – 1$$ zeros a mais de $$1$$ até ele do que $$pref[i]$$.
- Se $$v[i] = 1$$, como no caso anterior, basta procurarmos a ultima posição $$x$$, no vetor $$pref$$, que possui valor igual a $$pref[i] + k$$.
Chame de $$val$$ o valor da posição que queremos achar. Para o valor utilizaremos uma lower bound no valor $$val+1$$, e depois descontamos 1 da posição encontrada.
Após isso, basta checar se o intervalo de $$i$$ até $$x$$ é o maior até agora, se sim, atualizo a resposta.
Depois de rodar esse algoritmo para todas as $$N$$ posições de $$v$$, imprimimos a resposta e atualizamos o intervalo que foi mudado para uns, e printamos o vetor $$v$$
Segue código solução para maior compreensão:
https://gist.github.com/samyravitoria/bbf4d1bcc5e784bd9bdb51d116603489