Контест Senior Задачи на Java обновлено
Разбить массив на k частей
Условие
Разбейте массив неотрицательных чисел на не более чем k непрерывных непустых частей так, чтобы максимальная сумма части была как можно меньше. Выведите эту минимальную возможную максимальную сумму.
Ввод: в первой строке n и k (1 ≤ k ≤ n ≤ 10⁴), во второй n чисел от 0 до 10⁹.
Вывод: одно число.
Пример
5 2
7 2 5 10 8
18
Как подойти
Бинарный поиск по ответу + жадная проверка.
Подсказки: 2
- Проверить «можно ли уложиться в L» легко жадно.
- Ответ монотонен: ищите его двоичным поиском.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.