Имя пользователя1,

выглядит это просто
входная очередь arr - это обычная FIFO очередь
рабочий элемент логически состоит из абака (разрядной сетки) обслуживающих кассиров,
с первоначально нулевыми значениями. Дальше ты добавляешь число из текущего входного элемента arr к той ячейке абака, в которой на текущий момент наименьшая накопленная сумма.
Общее время обслуживания находится поиском максимума на регистре-абаке.

Технически регистр обслуживания проще всего организовать в виде очереди с приоритетом Min.
тогда arr(i) всегда будет добавляться к минимальному (текущему свободному) регистру абака.
Время счета будет порядка N*K*Log(K) при больших N

т.е., при зафиксированном K, просто порядка N

N*Log(K) - ок

Что значит "К не зафиксировано"?
K является функцией от мгновенного значения N? - K = F(N(t),t)?
Тогда проще будет сразу сказать - что регистр для K бесконечный и используется нечто вроде фибоначчиевых очередей.

сортировка входной очереди desc по времени предполагаемого обслуживания - не спасёт отца русского очередистроения?

не-не.
К - параметр - по всем канонам.
А N - размер задачи.
как-то так должно быть...

Имя пользователя1,
гребенка [53534]
т.е. если i(1) - i(k) - индексы первично загружаемых на счётную доску размера (разрядности) k
элементов,
то за текущим максимумом i(1) должно идти к-1 оставшихся во входной очереди
минимальных по возрастанию.
И так до исчерпания входной очереди.
глубжее нету ни глаз ни мозга ни времени разглядывать...

я сказал не то, что хотел (;

гребенка конечно здесь [53345]
т.е. - выбирается максимальный arr(i) и ставится в место (1) - i(1),
за которым из оставшихся во входной очереди выбирается последовательность минимальных
2..m таких, что сумма S их времен обслуживания <=arr(i(1))
Это первый пакет,
далее в той же последовательности - выбираем максимальный из оставшихся и к нему серию минимальных.

booby,
общая идея состоит в том, что минимальное время обслуживания получится тогда, когда
минимизируется разница между минимальным и максимальным накопленным значением в регистрах счётчика-обслуживателя-абака.
Для этого необходимо обеспечить нечто, похожее на "равномерную" загрузку разрядов,
так, чтобы по мере сложения на счётчике ни в каком разряде не образовывалось (при бесконечном времени работе, пакетированном на N элементов за шаг бесконечного времени)
значений сильно отличающихся от значений в других разрядах счётчика.
Нечто вроде идеи складывания равного с равным, но вот в такой револьверной подкрутке.

по смыслу эта ссылка где-то рядом.
По крайней мере, в разностной формулировке - выглядит совсем похоже.

Мне продолжает пока казаться на бегу, что примерно то, что я пытался сказать, должно само
давать результат близкий к оптимальному.

С поправкой на то, что после выбора текущего максимального из оставшейся очереди надо выбирать минимальные не пока их сумма меньше первого выбранного, а до тех пор, пока
сумма выбираемых минимальных впервые не превысит первый выбранный для "пакета" максимальный.

В таком виде алгоритм не зависит от K как параметра.
Это само по себе выглядит симпатичным.
Так как однотипно позволяет организовывать нагрузку для произвольного счётчика обслуживания произвольной разрядности K.

Вопрос здесь в том, какая структура эффективно позволит выбирать из себя сначала максимальный элемент, а затем последовательность минимальных.
этакая максимально-минимальная очередь.

Кстати, там где на самом деле именно мерж требуется, он как раз хорошо производится именно на абаках.
Позволяя при переносе списка из разряда в разряд, всегда складывать списки равного размера. Равномерное деление надвое как раз обеспечивает логарифмический результат сложения.
и наоборот - складывание равного с равным, дает логарифмическое число шагов алгоритма.
Я точно этой идеей руководствовался, в попытках здесь что-то бормотать между делом.