Приз, який ніхто не може виграти#9878

Приз, який ніхто не може виграти (Розбір)

Відсортуємо вартості товарів за неспаданням. Нехай в акції беруть участь товари з вартостями $c_{1} \leq c_{2} \leq ... \leq c_{k}$ c_1 \le c_2 \le ... \le c_k. Покупцю найвигідніше придбати два найдорожчі з них — $c_{k - 1}$ c_{k−1} та $c_{k}$ c_k. Якщо $c_{k - 1} + c_{k} > x$ c_{k−1} + c_k > x, він отримає ріг єдинорога в подарунок.

Нехай $a_{1}, a_{2}, ..., a_{n}$ a_1, a_2, ..., a_n — відсортовані вартості всіх $n$ товарів. Тоді до акції слід включити товари з вартостями $a_{1}, a_{2}, ..., a_{k}$ a_1, a_2, ..., a_k, де $k$ — найбільший індекс, для якого $a_{k - 1} + a_{k} \leq x$ a_{k−1} + a_k \le x.

Приклад

У першому прикладі відсортовані вартості: ${1, 2, 3, 4, 5}$ \{1, 2, 3, 4, 5\}. Оскільки $x = 6$ x = 6, шукаємо найбільший індекс $k$ , для якого $a_{k - 1} + a_{k} \leq 6$ a_{k−1} + a_k \le 6. Це $k = 3$ k = 3, оскільки $2 + 3 \leq 6$ 2 + 3 ≤ 6, але $3 + 4 > 6$ 3 + 4 > 6.

У другому прикладі відсортовані вартості: ${1, 4, 7, 8, 9}$ \{1, 4, 7, 8, 9\}. Оскільки $x = 10$ x = 10, найбільший індекс $k$ дорівнює $2$ : $1 + 4 \leq 10$ 1 + 4 \le 10, але $4 + 7 > 10$ 4 + 7 > 10.

Реалізація алгоритму

Зчитуємо вхідні дані.

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

Сортуємо вартості товарів за неспаданням.

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

Перебираємо пари сусідніх товарів $i$ та $i + 1$ i + 1. Щойно $v_{i} + v_{i + 1} > x$ v_i + v_{i+1} > x, товар вартістю $v_{i + 1}$ v_{i+1} та всі наступні за ним вже не можна включати до акції.

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

Тоді максимальна кількість товарів в акції дорівнює $i + 1$ i + 1 (нумерація починається з нуля).

    res = i + 1;
    break;
  }

Виводимо відповідь.

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