9878. Приз который никто не может выиграть

 

После торжественного открытия нового Бутик-магазина, к разочарованию Вы обнаруживаете, что не делаете столько продаж, сколько ожидали. Чтобы исправить это, Вы решили запустить специальное предложение. Вы помечаете некоторое подмножество n предметов для продажи как участвующих в предложении, и если люди купят ровно два из этих предметов, а также их стоимость будет строго больше чем х евро, то Вы дадите им рог единорога бесплатно!

Так как Вы недавно узнали, что все рога единорога действительно являются бивнями нарвала, то решаете сфальсифицировать предложение, выбирая участвующие предметы таким образом, что никто не сможет заработать рог в любом случае.

Чтобы никто Вас не заподозрил, Вы хотите выбрать как можно больше предметов, участвующих в предложении.

 

Вход. Первая строка содержит два целых числа: n (1 ≤ n ≤ 105) – количество предметов выставленных в магазине на продажу, и x (1 ≤ x ≤ 109) – минимальная стоимость указанная в условии. Вторая строка содержит n натуральных чисел, не больших 109. Это стоимости товаров в магазине.

 

Выход. Выведите максимальное количество предметов, которое можно выбрать как часть Вашего специального предложения чтобы никто не смог получить рог.

 

Пример входа 1

Пример выхода 1

5 6

1 2 3 4 5

3

 

 

Пример входа 2

Пример выхода 2

5 10

4 8 1 9 7

2

 

 

РЕШЕНИЕ

жадность

 

Анализ алгоритма

Отсортируем стоимости товаров в магазине. Пусть для специального предложения выбрано подмножество предметов со стоимостями c1, c2, …, ck. Тогда покупателю выгодно приобрести товары с наибольшими стоимостями ck-1 и ck. Если ck-1 + ck > х, то он бесплатно получит рог единорога.

Пусть a1, a2, …, an – отсортированные стоимости всех n товаров. Тогда для специального предложения следует выбрать товары со стоимостями a1, a2, …, ak, где k – такой наибольший индекс, что ak-1 + ak ≤ х.

 

Пример

В первом примере отсортируем товары: {1, 2, 3, 4, 5}. Поскольку х = 6, ищем такой наибольший индекс k, что ak-1 + ak ≤ 6. Им будет k = 3, так как 2 + 3 ≤ 6, но  3 + 4 > 6.

 

Отсортируем товары во втором примере: {1, 4, 7, 8, 9}. Поскольку х = 10, то наибольший индекс k равен 2, так как 1 + 4 ≤ 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. Как только vi + vi+1 > x, то товар стоимостью vi+1 уже не следует включать в специальное предложение.

 

res = n;

for (i = 0; i + 1 < n; i++)

  if (v[i] + v[i + 1] > x)

  {

 

Максимальное количество предметов в специальном предложении составит i + 1 (нумерация предметов стартует с 0).

 

    res = i + 1;

    break;

  }

 

Выводим ответ.

 

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