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");
	}

view raw noic-solucao-intermediario-s66.cpp hosted with ❤ by GitHub