Рассмотрим ленточный конвейер, на котором загружено много предметов. Когда предметы сходят с пояса, они загружаются в грузовики. Все грузовики одинаковы и могут перевозить предметы до определенного максимального веса (называемого грузоподъемностью грузовика). Элементы пронумерованы от 1 и имеют различный вес.
Предметы должны быть последовательно загружены в грузовики, то есть элементы с 1 по N (для некоторых N) идут на первом грузовике, элементы N + 1,…, M (для некоторых M) идут на втором грузовике и так далее. Конечно, не все грузовики будут загружены на полную мощность, но гарантируется, что ни один предмет не будет слишком тяжелым для грузовика.
Мы можем загружать грузовики жадным образом (загружать столько грузовиков, сколько сможете, в этот грузовик, а когда следующий товар не помещается, запустить новый грузовик), но это может привести к несбалансированному распределению предметов среди грузовиков.
Определяем запасную вместимость конвоя как сумму квадратов неиспользованной вместимости каждого грузовика в конвое. Мы хотим загружать грузовики таким образом, чтобы минимизировать запасную вместимость конвоя.
Учитывая грузоподъемность, c, грузовиков и последовательность весов предметов, сколько предметов должен перевозить каждый грузовик, и сколько грузовиков требуется?
В первой строке данных указано значение c и количество элементов n (<= 1000). Последующие строки содержат n значений, вес предметов по порядку. Некоторые примеры данных: </p>
6 5
1 2 3
1 1
Вывод: в первой строке выведите количество требуемых грузовиков. Во второй строке выведите количество элементов на каждом грузовике, начиная с количества элементов на первом грузовике, затем количество элементов на втором грузовике и т. Д. В последней строке выведите оставшуюся емкость состава. Для приведенных выше данных вы должны вывести:
2
2 3
10
Буду очень признателен за любые идеи, как решить эту проблему.