массив, распределение суммы как можно более равномерно

[рони]

вариант на котором остановился, если есть замечания напишите, всем откликнушимся большое спасибо!!!

<script>
function allocate(input, total) {
  const output = [];
  const length = input.length;
  const order = input.map((value, index) => ({value,index}));
  const sortedOrder = order.sort((a, b) => a.value - b.value);
  for (let i = 0; i < length; i++) {
    let {value,index} = sortedOrder[i];
    let num = Math.floor(total/(length - i))
    if(num > value) num = value;
    total -= num;
    output[index] = num
  }
  return output
};

let input = [5,10,0,12];
for (let total = 0; total < 41; total++) {
    let output = allocate(input, total)
    document.write(`${total}=>${output}<br>`)
}
  </script>

[Alexandroppolus]

если есть замечания напишите

Можно немного уменьшить объём вспомогательной памяти, если создать отсортированную копию интпута, по ней за один обход вычислить максимум, за второй обход уже расставить значения. Тогда, вроде бы, и арифметика вся будет целочисленной, без делений и округлений

[Белый шум]

Alexandroppolus,
Максимум можно получить с помощью Math.max(), но чем это поможет - что-то не вдупляю.

рони,
Проход хоть и один, но для каждого элемента массива выполняется деление - сложная операция, по идее. Хотя я хз как там процессоры внутри работают, может им это и проще чем пару лишних проходов сделать.

[рони]

Alexandroppolus,

если создать отсортированную копию интпута

есть sortedOrder

вычислить максимум

max = sortedOrder.slice(-1)[0].value

и как это использовать?

[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}`);
}

см. консоль

[рони]

Alexandroppolus,