Solução Informática - Nível Iniciante - Semana 3

Solução por Lúcio Figueiredo

Conhecimentos prévios necessários:

Inicialmente, vamos ordenar as alturas de cada pessoa em ordem crescente. Perceba que, é sempre ótimo formar o maior número de duplas possível. Além disso, se a quantidade de duplas que formamos é $k$ , ou seja, então a melhor opção é usar as $k$ pessoas mais baixas em cada dupla. Isto é verdade pois, desta maneira, estamos reduzindo ao máximo a soma de cada dupla.

Usando esse fato, vamos iterar pelo vetor ordenado e aumentar a nossa variável de resposta (que inicialmente tem valor $0$ ) sempre que conseguirmos fazer uma dupla com a pessoa sendo considerada no momento.

O que resta descobrir é como escolher a segunda pessoa em cada dupla de maneira ótima. Note que, como iteramos por cada pessoa em ordem crescente de altura, a medida que avançamos no vetor, a quantidade de pessoas que podem ser utilizadas para formar uma dupla diminui. Ou seja, sendo $i$ o índice da pessoa que estamos considerando para uma dupla no momento, a quantidade de índices $j$ tais que $h[i] + h[j] \leq x$ diminui.

Logo, ao considerar uma pessoa de índice $i$ , a melhor opção é escolher o índice $j$ de forma que $h[j]$ é a maior altura tal que $h[i] + h[j] \leq x$ , pois, desta maneira, restringimos minimamente a quantidade de escolhas possíveis para os índices futuros. Caso tal índice $j$ não exista, já encontramos a quantidade máxima possível de duplas que conseguimos formar. As pessoas restantes, (as que não estão em uma dupla) irão entrar no brinquedo sozinhas, logo, aumentamos a nossa resposta nessa quantidade de pessoas.

O algoritmo que indicamos acima para resolver o problema é um exemplo de algoritmo guloso. Como podemos implementá-lo? Vamos usar um técnica de dois ponteiros (ou two pointers), da seguinte forma:

O ponteiro indicado por $l$ irá iterar de $1$ a $N$ , e representará o índice da pessoa atual que está sendo considerada para uma dupla. Já o ponteiro $r$ irá iterar de $N$ a $1$ , e representará a pessoa que estamos considerando para fazer uma dupla com $l$ . Existem dois casos:

Caso 1: $h[l] + h[r] \leq x$ . Neste caso, conseguimos fazer uma dupla com $l$ e $r$ (de forma que $h[r]$ é maior possível, já que ordenamos $h$ ), e assim, aumentamos o índice $l$ e diminuímos $r$ para tentar formar duplas futuras, lembrando de aumentar a variável de resposta, pois criamos uma dupla.
Caso 2: $h[l] + h[r] > x$ . Neste caso, diminuiremos o índice $r$ , já que estamos tentando encontrar um índice $r$ que possa formar uma dupla com $l$ . Como o índice $r$ não estará em dupla alguma, aumentamos nossa resposta também (já que $r$ entrará no brinquedo sozinho).

Assim, concluímos o nosso algoritmo, com complexidade final $O(N \log_{} N)$ , já que precisamos ordenar o vetor de entrada e a complexidade do algoritmo de dois ponteiros é $O(n)$ (pois cada ponteiro itera pelos números de $1$ a $N$ ).

Confira o código abaixo para melhor entendimento:

	// Problemas da Semana Noic - Nível Iniciante - Semana 3
	// Problema: Alturas
	// Complexidade: O(N log N)

	#include <bits/stdc++.h>

	using namespace std;

	// tamanho máximo do vetor
	const int maxn = 2e5+10;

	int h[maxn];

	int main(void)
	{
	int n, x;
	scanf("%d %d", &n, &x);

	for (int i = 1; i <= n; i++)
	scanf("%d", &h[i]);

	// ordenamos o vetor em O(N log N)
	sort(h+1, h+n+1);

	int l = 1, r = n; // ponteiros
	int ans = 0; // resposta do problema

	while (l <= r) // se l > r, podemos finalizar o algoritmo
	{
	if (h[l]+h[r] <= x) // caso 1
	{
	l++, r--;
	ans++; // conseguimos formar uma nova dupla
	}
	else
	{
	r--; // caso 2
	ans++; // r fica sozinho
	}
	}

	printf("%d\n", ans);
	}

view raw

alturas.cpp

hosted with ❤ by GitHub