Низька потужність

Ви проектуєте сучасні чіпи для машин. Виробництво чіпів нескладне, але живлення є складністю, оскільки доступні батареї мають різні вихідні потужності.

Уявіть, що у вас є $n$ машин, кожна з яких має два чіпи. Кожен чіп потребує $k$ батарей для роботи. Не важливо, яку сумарну потужність отримує чіп, але машина працює найкраще, коли вихідні потужності її двох чіпів якомога ближчі одна до одної. Вихідна потужність чіпа — це мінімальна потужність серед його $k$ батарей.

Усього у вас є $2nk$ батарей, і слід розподілити їх між чіпами. Можливо, неможливо розподілити батареї так, щоб у кожній машині вихідні потужності двох чіпів були однакові. Однак треба розподілити батареї так, щоб для всіх машин різниця вихідних потужностей чіпів була мінімальною. Тобто, ви хочете гарантувати замовникам, що різниця вихідних потужностей чіпів у кожній машині не перевищує $d$, і при цьому $d$ є якомога меншою. Для цього слід знайти оптимальний розподіл батарей між чіпами.

Розглянемо приклад 1. Є $2$ машини, кожна з яких потребує $3$ батареї на чіп, а батареї мають потужності 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Наприклад, можна розподілити батареї так: $1,3,5$ до одного чіпа, $2,4,12$ — до іншого чіпа тієї ж машини; $6,8,9$ — до третього чіпа, $7,10,11$ — до четвертого. Вихідні потужності чіпів будуть 1, 2, 6, 7, і різниця у потужностях кожної машини дорівнює $1$. Зверніть увагу, що цього результату можна досягти й іншими шляхами.