Контест Senior Куча обновлено
k-я по величине сумма пар из двух списков
Условие
Даны два отсортированных по неубыванию массива a (длины n) и b (длины m). Рассмотрим все n · m сумм aᵢ + bⱼ (по одной на каждую пару индексов). Найдите k-ю по величине из них, если выписать их по неубыванию.
Ввод: в первой строке n, m, k (1 ≤ n, m ≤ 2500, 1 ≤ k ≤ min(n·m, 2500)), во второй a, в третьей b. Все числа от 0 до 10⁹.
Вывод: k-я сумма.
Пример 1
Ввод:
3 3 4
1 7 11
2 4 6
Вывод:
9
Пример 2
Ввод:
2 2 4
1 1
1 1
Вывод:
2
Как подойти
Подсказки: 2
- Представьте суммы таблицей n × m: строки и столбцы отсортированы.
- Как в слиянии k отсортированных списков: в куче по одному кандидату от строки.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.