Здравствуйте, Chorkov, Вы писали:

C>Здравствуйте, RiNSpy, Вы писали:

RNS>>А почему O(K ln(K))? Это самая интересная часть.

C>[...]

Отлично! Имхо, это правильный ответ (вместе с вашим предыдущим постом).

Здравствуйте, RiNSpy, Вы писали:

RNS>Задача — распределить игроков по командам так, чтобы все команды были как можно более одинаковы. Т.е. нужно минимизировать максимальное отклонение от среднего уровня.

1) часть после "Т. е." это часть условия задачи? Тогда зачем то, что было до?
2) Если же это уже не условие, а твоя интерпретация, то условие "как можно более одинаковы" может выражаться по разному. Например как сумма квадратов отклонений.

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

Общий метод тут, IMHO, применить что-то вроде дифференциальной эволюции.
Весь вопрос, как производить скрещивание.
При ДЭ для скрещивания мы берём 3 особи: A, B, C, вычисляем разницу В и С, как-то её случайно масштабируем, и применяем к А.

В данном случае можно поступить, например, так.

По В и С мы определяем какое множество игроков ещё не точно привязано к командам, и дальше пробуем их как-то случайно переставить, с сохранением численностей команд. Может быть будет лучше, если мы будем брать только такие перестановки, которые улучшают аутсайдера.