Контест Middle Задачи на Java спрашивают часто обновлено
Пары с суммой не больше S
Условие
Дан массив целых чисел. Посчитайте количество пар индексов i < j, для которых a[i] + a[j] ≤ S.
Ввод: в первой строке n и S (1 ≤ n ≤ 2·10⁴, |S| ≤ 2·10⁹), во второй n чисел по модулю до 10⁹.
Вывод: одно число.
Пример
5 6
1 5 3 2 4
6
Как подойти
Сортировка и два указателя с концов.
Подсказки: 2
- Отсортируйте массив.
- Если a[i] + a[j] ≤ S, сколько пар с этим i подходит сразу?
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.