Максимальное время одновременной работы процессоров

Зачем это в ЕГЭ.
Задание 22 в ЕГЭ по информатике проверяет умение анализировать параллельные вычисления и определять минимальное или максимальное время выполнения задач. Даёт 1 первичный балл. Встречается в ~30% вариантов ФИПИ, часто в комбинации с темами по обработке данных или алгоритмам.

Главная идея.
Задача сводится к оптимальному распределению процессов между процессорами так, чтобы завершить все задачи за минимальное время. Ключ — найти «узкое место»: либо самый долгий процесс, либо равномерно распределить нагрузку.

Алгоритм (чеклист).
1. Выписать все времена выполнения процессов.
2. Если процессоры работают параллельно без ограничений, максимальное время — это время самого долгого процесса.
3. Если процессоров меньше, чем процессов, суммировать времена, распределяя их поровну.
4. Проверить, не превышает ли суммарное время на одном процессоре максимальное из одиночных процессов.
5. Выбрать наибольшее значение из шагов 2 и 4.

Опоры (кратко).
- Максимальное время без ограничений: $\max(t_1, t_2, \dots, t_n)$.
- При $k$ процессорах: $\max\left(\max(t_i), \frac{\sum t_i}{k}\right)$.
- Округление всегда вверх: $\lceil \frac{a}{b} \rceil$.

Пример 1 (базовый подтип)
Дано: 3 процесса с временами 4, 6, 8 секунд. 2 процессора.
Шаг 1. Времена: 4, 6, 8.
Шаг 2. Максимальное одиночное время: 8.
Шаг 3. Суммарное время: 4 + 6 + 8 = 18. На 2 процессорах: 18 / 2 = 9.
Шаг 4. Сравниваем: 9 > 8.
Шаг 5. Ответ: 9.

Пример 2 (усложнённый подтип)
Дано: 5 процессов: 2, 3, 5, 7, 11. 3 процессора.
Шаг 1. Времена: 2, 3, 5, 7, 11.
Шаг 2. Максимальное одиночное: 11.
Шаг 3. Сумма: 2 + 3 + 5 + 7 + 11 = 28. На 3 процессорах: $\lceil 28 / 3 \rceil = 10$.
Шаг 4. 10 < 11.
Шаг 5. Ответ: 11.

Типичные ошибки.
1. Игнорирование самого долгого процесса — если он длиннее среднего.
2. Неправильное округление — забывают округлять вверх.
3. Путаница с количеством процессоров — подставляют число процессов вместо процессоров.
4. Неучёт всех процессов — пропускают один из элементов списка.

Дальше.
Разбери задачи на динамическое программирование для распределения ресурсов.