Разбор
Отсортируем рейтинги программистов в массиве . Поиск двух программистов с максимальным суммарным рейтингом будем осуществлять при помощи техники двух указателей.
Инициализируем указатель на начало массива и указатель на конец массива.
Среди всех возможных сумм , не превышающих , находим максимальную. Если , сдвигаем указатель вперед. В противном случае сдвигаем указатель назад. Процесс передвижения указателей продолжаем до тех пор, пока они не встретятся.
Пример
Рассмотрим второй тест. Отсортируем числа и инициализируем указатели. Промоделируем работу алгоритма. В данном случае : ищем два числа с максимальной суммой, не превышающей .
Реализация алгоритма
Читаем входные данные.
scanf("%d %d", &n, &m); v.resize(n); for (i = 0; i < n; i++) scanf("%d", &v[i]);
Сортируем рейтинги программистов.
sort(v.begin(), v.end());
Инициализируем указатели. В переменной вычисляем максимальную сумму двух элементов.
int mx = -1, low = 0, high = n - 1;
Указатель двигаем вперед, указатель двигаем назад.
while (low < high) {
Среди всех возможных сумм , не больших , находим максимум. Если , то двигаем вперед . Иначе двигаем назад .
if (v[low] + v[high] <= m) { mx = max(mx, v[low] + v[high]); low++; } else high--; }
Выводим ответ.
printf("%d\n", mx);