[Alexandroppolus]

рони,
я про тот "максимум", который можно отсыпать в output[i]

вот, изобразил слова в г-коде. Идея в принципе та же, но нет деления на каждой итерации (есть только целочисленное умножение), и дополнительной памяти только массив целых чисел, а не массив объектов. Не знаю, насколько это сможет ускорить, проверять было лень

function allocate(input, total) {
    var output = [];
    var length = input.length;
    var sortedInput = input.slice().sort(function (a, b) { return a - b; });
    var lastValue = 0;
    var maxH = 0;
    var remainder = 0;

    for (var i = 0; total > 0 && i < length; ++i) {
        var item = sortedInput[i];
        var height = item - lastValue;
        if (height > 0) {
            lastValue = item;
            var width = length - i;
            var area = width * height;
            if (total < area) {
                height = Math.floor(total / width);
                remainder = total % width;
            }
            maxH += height;
            total -= area;
        }
    }
    for (var i = 0; i < length; ++i) {
        var item = input[i];
        output.push(item > maxH ? maxH + (--remainder >= 0 ? 1 : 0) : item);
    }
    return output
}

// проверка для разных total
var input = [5,10,0,12, 7, 3];
for (var total = 0; total < 41; total++) {
    var output = allocate(input, total);
    console.log(`${total} => ${output}`);
}

см. консоль