El premio que nadie puede ganar (Editorial)

Ordenemos los costos de los productos de forma no decreciente. Supongamos que en la promoción participan productos con costos c_1 \le c_2 \le ... \le c_k. Al comprador le resulta más conveniente adquirir los dos más caros de ellos — c_{k−1} y c_k. Si c_{k−1} + c_k > x, recibirá el cuerno de unicornio de regalo.

Sean a_1, a_2, ..., a_n los costos ordenados de todos los $n$ productos. Entonces en la promoción deben incluirse los productos con costos a_1, a_2, ..., a_k, donde $k$ — es el mayor índice para el cual a_{k−1} + a_k \le x.

Ejemplo

En el primer ejemplo, los costos ordenados son: \{1, 2, 3, 4, 5\}. Dado que x = 6, buscamos el mayor índice $k$ para el cual a_{k−1} + a_k \le 6. Este es k = 3, ya que 2 + 3 ≤ 6, pero 3 + 4 > 6.

En el segundo ejemplo, los costos ordenados son: \{1, 4, 7, 8, 9\}. Dado que x = 10, el mayor índice $k$ es igual a $2$: 1 + 4 \le 10, pero 4 + 7 > 10.

Implementación del algoritmo

Leemos los datos de entrada.

scanf("%d %d", &n, &x);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Ordenamos los costos de los productos de forma no decreciente.

sort(v.begin(), v.end());

Recorremos los pares de productos vecinos $i$ e i + 1. Tan pronto como v_i + v_{i+1} > x, el producto con costo v_{i+1} y todos los siguientes a él ya no pueden incluirse en la promoción.

res = n;
for (i = 0; i + 1 < n; i++)
  if (v[i] + v[i + 1] > x)
  {

Entonces la cantidad máxima de productos en la promoción es igual a i + 1 (la numeración comienza desde cero).

    res = i + 1;
    break;
  }

Mostramos la respuesta.

printf("%d\n", res);