Il premio che nessuno può vincere#9878

Il premio che nessuno può vincere (Editoriale)

Ordiniamo i prezzi dei prodotti in ordine non decrescente. Supponiamo che nella promozione partecipino prodotti con prezzi $c_{1} \leq c_{2} \leq ... \leq c_{k}$ c_1 \le c_2 \le ... \le c_k. Per l'acquirente è più conveniente acquistare i due più costosi tra questi — $c_{k - 1}$ c_{k−1} e $c_{k}$ c_k. Se $c_{k - 1} + c_{k} > x$ c_{k−1} + c_k > x, riceverà il corno di unicorno in regalo.

Siano $a_{1}, a_{2}, ..., a_{n}$ a_1, a_2, ..., a_n i prezzi ordinati di tutti gli $n$ prodotti. Allora nella promozione bisogna includere i prodotti con prezzi $a_{1}, a_{2}, ..., a_{k}$ a_1, a_2, ..., a_k, dove $k$ — è l'indice massimo per cui $a_{k - 1} + a_{k} \leq x$ a_{k−1} + a_k \le x.

Esempio

Nel primo esempio, i prezzi ordinati sono: ${1, 2, 3, 4, 5}$ \{1, 2, 3, 4, 5\}. Poiché $x = 6$ x = 6, cerchiamo l'indice massimo $k$ per cui $a_{k - 1} + a_{k} \leq 6$ a_{k−1} + a_k \le 6. Questo è $k = 3$ k = 3, poiché $2 + 3 \leq 6$ 2 + 3 \le 6, ma $3 + 4 > 6$ 3 + 4 > 6.

Nel secondo esempio, i prezzi ordinati sono: ${1, 4, 7, 8, 9}$ \{1, 4, 7, 8, 9\}. Poiché $x = 10$ x = 10, l'indice massimo $k$ è uguale a $2$ : $1 + 4 \leq 10$ 1 + 4 \le 10, ma $4 + 7 > 10$ 4 + 7 > 10.

Implementazione dell'algoritmo

Leggiamo i dati di input.

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

Ordiniamo i prezzi dei prodotti in ordine non decrescente.

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

Scorriamo le coppie di prodotti adiacenti $i$ e $i + 1$ i + 1. Non appena $v_{i} + v_{i + 1} > x$ v_i + v_{i+1} > x, il prodotto con prezzo $v_{i + 1}$ v_{i+1} e tutti quelli successivi non possono più essere inclusi nella promozione.

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

Allora il numero massimo di prodotti nella promozione è uguale a $i + 1$ i + 1 (la numerazione inizia da zero).

    res = i + 1;
    break;
  }

Stampiamo la risposta.

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