noic-iniciante-semana3.cpp

alturas.cpp

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