Solução Informática - Nível Intermediário - Semana 4

Solução por Thiago Mota

Conhecimento prévio necessário:

• Mapa
• Vetores

Nós temos um vetor $a_i$ e temos que fazer todos os números deles virarem $0$ com o menor número de operações. A soma do vetor $a_i$ é $0$.

Nós podemos dividir o vetor em partes consecutivas de elementos com soma zero. Se a parte tem tamanho $l$ nós podemos usar todos os pares de vizinhos e transformar tudo em zero com $l - 1$ operações.

Então, a soma do número de operações em cada uma dessas partes gera uma resposta $ans = n - k$ onde $k$ é o número de partes. Então para minimizar a resposta temos que maximizar o número de partes.

Vamos calcular a soma de prefixos. Como as partes que nós procuramos tem soma zero, o prefixo no início e no final de cada uma será igual, logo podemos calcular a maior frequência entre todos os prefixos, a maior frequência será o número de partes que iremos dividir, logo a resposta é $n - f$ sendo $f$ a maior frequência. Segue o código:

	#include <bits/stdc++.h>
	using namespace std;
	const int maxn = 2e5 + 10;
	int n;
	map<long long, int> freq;
	int32_t main() {
	cin >> n;
	long long s=0;
	int ans = n - 1;
	for(int i=1;i<=n;i++) {
	int x;
	cin >> x;
	s += x;
	freq[s]++;
	ans = min(ans, n - freq[s]);
	}
	cout << ans << "\n";
	return 0;
	}

view raw money.cpp hosted with by GitHub