Solução Informática Intermediário - Semana 66

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:

// Noic - Problemas da Semana 66
// Nivel Intermédiario
// Solução por Samyra Almeida
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
int n, k, pref[maxn], v[maxn];
int busca(int val) // faço a busca binária do tipo lower bound, ou seja, que ira retornar a posição da 1 aparição de val.
{
int ini = 1, fim = n, pos = n+1;
while(ini <= fim)
{
int mid = (ini + fim) >> 1;
if(pref[mid] >= val)
{
pos = mid;
fim = mid - 1;
}
else
{
ini = mid + 1;
}
}
return pos;
}
int main()
{
scanf("%d %d", &n, &k);
for(int i = 1 ; i <= n ; ++i)
{
cin >> v[i];
pref[i] = pref[i - 1] + (!v[i]); // monto a soma de prefixos.
}
int ini = 0, fim = 0;
for(int i = 1 ; i <= n ; ++i)
{
int x;
if(v[i]) // se v[i] = 1.
{
x = busca(pref[i] + k + 1); // faço a busca da posição, como foi explicado acima.
}
else // se v[i] = 0.
{
if(k == 0) continue; // se não consigo mudar ninguem, ignoro esse caso.
x = busca(pref[i] + k); // faço a busca da posição, como foi explicado acima.
}
if(x - i >= fim - ini + 1) // checo se o intervalo que eu achei é maior que a minha resposta atual, vale lembrar que:
{ // x - 1 é o final do intevalo, portanto fica x - 1 - i + 1 = x - i.
ini = i;
fim = x - 1;
}
}
if(ini == 0 && fim == 0) printf("0\n"); // esse caso acontece se não existir nenhum 0 no vetor ou se k = 0
else printf("%d\n", fim - ini + 1); // se não imprimo o tamanho do intervalo de uns.
if(ini != fim || (ini == fim && k > 0 && ini != 0)) // se ini e fim são posições diferentes ou se ini = fim e eu consigo
{ // mudar aquela posição e ini não é 0, mudo o intervalo para uns.
for(int i = ini ; i <= fim ; ++i)
v[i] = 1;
}
for(int i = 1 ; i <= n ; ++i) printf("%d ", v[i]); // imprimo o vetor final.
printf("\n");
}