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:
https://gist.github.com/luciocf/23cc9f4e9507989c7eb35ed3fd96b996