11664. Разбиение массива

Задан массив из 2n целых чисел.

Сгруппируйте эти числа в n пар (a₁, b₁), (a₂, b₂), ..., (a_n, b_n) так чтобы сумма min(a_i, b_i) для всех i была наибольшей.

Вход. Первая строка содержит одно число n (n ≤ 10⁵). Вторая строка содержит 2n целых чисел, каждое из которых по модулю не больше 10⁵.

Выход. Выведите наибольшее возможное значение суммы

Пример входа	Пример выхода
2 4 1 3 2	4

РЕШЕНИЕ

жадность

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

Пусть x₁ ≤ x₂ ≤ … x_2n – отсортированный массив. Разбиение на пары его элементов проведем следующим образом: (x₁, x₂), (x₃, x₄), …, (x_2n-1, x_2n). Тогда искомая сумма равна сумме элементов отсортированного массива с нечетными индексами:

min(x₁, x₂) + min(x₃, x₄) + … + min(x_2n-1, x_2n) = x₁ + x₃ + … + x_2n-1

Пример

Отсортированный массив имеет вид: (1, 2, 3, 4).

Разобьём числа на пары: (1, 2), (3, 4). Тогда искомая сумма будет равна

min(1, 2) + min(3, 4) = 1 + 3 = 4

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

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

scanf("%d", &n);

v.resize(2 * n);

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

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

Сортируем массив.

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

В переменной s вычисляем искомую сумму.

s = 0;

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

s += v[i];

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

printf("%lld\n", s);