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) - где М - максимально возможное число во входных данных. Это через бинпоиск по минимальному числу в конце.
