Парные рейсы: минимизировать худший перегруз

В городе после фестиваля нужно развезти жителей по районам. Для каждого из 2n районов известен прогноз пассажиропотока (целое число). Диспетчер запускает ровно n рейсов, и каждый рейс обслуживает ровно два района (то есть районы нужно разбить на пары).

Перегруз рейса равен сумме пассажиропотоков двух районов в его паре. Диспетчер хочет, чтобы самый перегруженный рейс получился как можно менее перегруженным.

Найдите, каким может быть минимально возможный перегруз самого перегруженного рейса.

Важно: значения могут не помещаться в 32-битный тип (как на олимпиадах), используйте 64-битные целые. В Python это не проблема.

Формат ввода

Первая строка: одно целое число n (1 ≤ n ≤ 5000). Вторая строка: 2n целых чисел a1, a2, …, a2n (0 ≤ ai ≤ 1 000 000) — пассажиропотоки районов.

Формат вывода

Выведите одно целое число — минимально возможное значение максимальной суммы внутри пары.

Ограничения

• 1 ≤ n ≤ 5000
• 0 ≤ ai ≤ 1 000 000
• Ответ может быть больше 2^31 − 1.

Пример

Ввод:

3
1 2 3 4 5 6

Вывод:

7

Пояснение: можно сделать пары (1,6), (2,5), (3,4). Суммы: 7, 7, 7, значит худший перегруз = 7, и меньше уже нельзя.

Ключевое наблюдение: нас волнует не сумма всех, а максимальная сумма среди пар (минимакс). Если какой-то большой район поставить в пару не с самым маленьким, то его партнёр будет не меньше, а значит эта пара станет только тяжелее — и именно она часто определяет «худший рейс».

Приём: жадная стратегия после сортировки. Отсортируем значения. Дальше делаем пары так: самый маленький с самым большим, второй маленький со вторым большим и т.д. Идея почему это работает: пусть большие числа сидят в разных парах. Чтобы уменьшить максимум, каждому большому числу выгодно дать как можно меньшего партнёра. Любая «перестановка» партнёров среди двух больших и двух маленьких не может сделать максимальную сумму меньше, чем при паровании крайних.

План:

• Считай 2n чисел в массив.
• Отсортируй по возрастанию.
• Поставь два указателя: i = 0 (минимум) и j = 2n-1 (максимум).
• Пока i < j: посчитай сумму пары a[i] + a[j], обнови ответ как максимум из этих сумм, сдвинь i += 1, j -= 1.
• Выведи найденный максимум.

Сложность: сортировка O(n log n), проход указателями O(n).

Частая ошибка: после сортировки «соседей» паровать вместе (1-й со 2-м, 3-й с 4-м) — это обычно увеличивает максимальную сумму. Также в других языках не забудь про 64-битные целые; в Python переполнения нет.