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

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

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

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

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

Формат ввода

Первая строка: одно целое число t (1 ≤ t ≤ 4) — количество наборов данных.

Далее идут t наборов данных. Каждый набор задан в следующем формате:

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

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

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

Ограничения

• 1 ≤ t ≤ 4
• 1 ≤ n ≤ 5000
• Сумма значений n по всем наборам данных не превышает 5000.
• 0 ≤ ai ≤ 1 000 000
• Ответ может быть больше 2^31 − 1.

Пример

Ввод:

3
1
0 0
1
0 1000000
2
0 10 10 10

Вывод:

0
1000000
20

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

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

План:

• Считай 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 переполнения нет.