Алгоритм максимально равномерного распределения предметов?

Question

[epitxx]

Допустим есть несколько списков каких-либо предметов, и еще один дополнительный список источник из которого они будут пополняться.
Все списки характеризуются целыми числами, которые обозначают количество предметов в них.
Нужно составить алгоритм на вход которому подается список числа предметов, и число предметов в источнике, а на выходе получается список с оптимизированным количеством предметов.
Думаю на примерах будет более понятно:
[30, 50, 350], 300 -> [190, 190, 350]
[30, 50, 350], 1001 -> [477, 477, 477]

Алгоритм желательно привести на каком-нибудь языков программирования.

Comments

[Василий Банников]

Нифига не понятно на самом деле, что дано, и что нужно получить.
И что такое " список с оптимизированным количеством предметов."

Максимально равномерное распределение - это когда всем поровну.

[Василий Банников]

UPD: Кажется понял. Поправьте, если неправильно.
Дано:
- последовательность N, состоящая из натуральных чисел N0, N1, N2 ... Nn
- Ещё одно натуральное число X
Каждое число представляет из себя количество чего-то.

Найти:
Последовательность из натуральных чисел N', у которой
N0' >= N0, N1' >= N1 ... Nn' >= Nn
И sum(N') = sum(N) + X
При этом чтобы разность max(N') и min(N') была минимальной

[epitxx]

Василий Банников, все верно

Answer 1

[Wataru]

std::vector<int> DistributeExtraObjectsFairly(std::vector<int> objects, int extra_objects) {
    std::vector<int> permutation;
    permutation.reserve(objects.size()+1);
    permutation.resize(objects.size());
    std::iota(permutation.begin(), permutation.end(), 0);
    std::sort(permutation.begin(), permutation.end(),
        [&objects](const int &a, const int &b) {return objects[a] < objects[b];});
    int num_increased = 1;
    permutation.push_back(0);
    int step = (objects[permutation[num_increased]] - objects[permutation[num_increased-1]]) * num_increased;
    while (extra_objects >= step && num_increased < objects.size()) {
        extra_objects -= step;
        ++num_increased;
        step = (objects[permutation[num_increased]] - objects[permutation[num_increased-1]]) * num_increased; 
    }
    int final_value = objects[permutation[num_increased-1]] + extra_objects / num_increased;
    int num_bigger_values = extra_objects % num_increased;
    for (int i = 0; i < num_bigger_values; ++i) {
        objects[permutation[i]] = final_value + 1;
    }
    for (int i = num_bigger_values; i < num_increased; ++i) {
        objects[permutation[i]] = final_value;
    }
    return objects;
}

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

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

Edit: работает за O(n log n), где n - количество элементов в списке. Быстрее, я подозреваю, никак. Есть еще решение за O(n log M) - где М - максимально возможное число во входных данных. Это через бинпоиск по минимальному числу в конце.

Answer 2

[rPman]

Сортируешь числа в списке предметов по возрастанию
Алгоритм добавления количества Z следующий:
* по очереди берешь равные по значению числа (пусть будет X, количество N) и следующий за ними не равный по значению (пусть будет Y), если такого нет то считаем это значение - бесконечным
* вычисляешь разницу Y-X, вычисляем, сколько можно дололжить к ним от Z - считаем если (Y-X)*N меньше или равно Z значит заменяем N первых чисел на Y, а из Z вычитаем (Y-X)*N, если (Y-X)*N больше Z (в т.ч. если Y - бесконечность) значит к этим первым N числам из списка прибавляем Z/N (если не делится на цело, значит берем целую часть от Z а затем остаток по 1 докидываем вторым проходом, Z обнуляем, завершаем работу алгоритма
* если Z не ноль, повторяем весь алгоритм

Answer 3

[Сергей Соколов]

Расставить начальные значения на оси.
Значение указывает на одно или больше «ведёрок» из начального массива, которые надо наполнять.
Двигаться слева направо, накапливая «вёдра», в которые льём.

На каждом шаге известно, сколько осталось запаса для разлива.
Есть «ёмкость» шага – кол-во вёдер умноженное на длину текущего шага.
Пока запас выше или равен ёмкости – добавляем в текущие вёдра поровну и к следующему шагу.
Потом, если что-то осталось – разделить поровну, округлив в бОльшую сторону, и по очереди раздавать по актуальным ведёркам.

JavaScript

далеко не оптимальный код, но, вроде, рабочий

function spread(arr, src) {
  const result = [...arr]; // копия исходного массива
  if (src <= 0) return result;

  const axis = {}; // value: [ids of bins]
  arr.forEach((v, i) => {
    if (!axis[v]) axis[v] = [];
    axis[v].push(i);
  });

  const keys = Object.keys(axis).sort((a, b) => a - b);

  const bins = [...axis[keys[0]]]; // ids of "bins" we're filling
  for (let i = 1; i < keys.length; i++) {
    const currentKey = keys[i];
    const prevKey = keys[i - 1];
    const diff = currentKey - prevKey;
    const capacity = bins.length * diff;
    
    if (src < capacity) break;

    bins.forEach(key => result[key] += diff);
    src -= capacity;
    bins.push(...axis[currentKey]);
  }

  if (src) {
    const want = Math.ceil(src / bins.length);
    bins.forEach(key => {
      const given = Math.min(src, want)
      result[key] += given;
      src -= given;
    });
  }

  console.log(result);
  return result;
}

spread([30, 50, 350], 300); // [ 190, 190, 350 ]
spread([30, 50, 350], 1001); // [ 477, 477, 477 ]
spread([130, 50, 50, 101], 800); // [ 282, 283, 283, 283 ]

Comments

[Wataru]

spread([1, 1, 1, 1, 1], 7); // [3, 3, 3, 2, 1], хотя должно быть [3, 3, 2, 2, 2]

У вас ошибка там, где вы оставшийся в конце src распределяете - надо не ceil брать, а floor. И еще остаток по +1 раздать потом, кому хватит.

Ну и еще, конечно, у вас решение за O(n^2) из-за bins.forEach(key => result[key] += diff); Можно вместо этого в конце всем затронутым числам дать склько нужно до последнего.