9632. Лучшая команда

Сегодня собрались n программистов. У каждого программиста есть рейтинг, показывающий его силу. Рейтинг – это целое число от 0 до 10⁹. Ваш рейтинг как программиста равен m. Со всех собравшихся сегодня программистов Вы хотите выбрать двух в свою команду. Их необходимо выбрать таким образом, чтобы сумма их рейтингов была максимальной, но не превышала Ваш рейтинг, поскольку Вы хотите быть лидером этой команды.

Вход. В первой строке заданы два целых числа: n (2 ≤ n ≤ 10⁵) – количество программистов и m (0 ≤ m ≤ 10⁹) – Ваш рейтинг. Во второй строке приведены n целых чисел r₁, r₂, ..., r_n (0 ≤ r_i ≤ 10⁹) – рейтинги программистов.

Выход. Выведите одно целое число – максимальную сумму рейтингов выбранных программистов или -1, если таких двух человек найти невозможно.

Пример входа 1	Пример выхода 1
5 8 5 3 4 6 5	8
Пример входа 2	Пример выхода 2
7 19 8 4 25 1 20 5 12	17
Пример входа 3	Пример выхода 3
4 76 38 41 39 40	-1

РЕШЕНИЕ

два указателя

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

Отсортируем рейтинги программистов в массиве v. Поиск двух программистов с максимальным суммарным рейтингом будем осуществлять при помощи техники двух указателей.

Инициализируем указатель low = 0 на начало массива и указатель high = n – 1 на конец массива.

Среди всех возможных сумм v[low] + v[high], не превышающих m, находим максимальную. Если v[low] + v[high] ≤ m, сдвигаем указатель low вперед. В противном случае сдвигаем указатель high назад. Процесс передвижения указателей продолжаем до тех пор, пока они не встретятся.

Пример

Рассмотрим второй тест. Отсортируем числа и инициализируем указатели. Промоделируем работу алгоритма. В данном случае m = 19: ищем два числа с максимальной суммой, не превышающей 19.

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

Читаем входные данные.

scanf("%d %d", &n, &m);

v.resize(n);

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

scanf("%d", &v[i]);

Сортируем рейтинги программистов.

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

Инициализируем указатели. В переменной mx вычисляем максимальную сумму двух элементов.

int mx = -1, low = 0, high = n - 1;

Указатель low двигаем вперед, указатель high двигаем назад.

while (low < high)

{

Среди всех возможных сумм v[low] + v[high], не больших m, находим максимум. Если v[low] + v[high] ≤ m, то двигаем вперед low. Иначе двигаем назад high.

if (v[low] + v[high] <= m)

{

mx = max(mx, v[low] + v[high]);

low++;

}

else high--;

}

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

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