spamsink | Оптимизационная задачка

Уж как переложил на бытовые реалии, так переложил.

Имеется поликлиника, в которых работают специалисты N разных профилей. Приходящие пациенты встают в общую очередь. Сами они объяснить, какой врач им нужен, не могут, а в ответ на вопрос "К такому-то есть кто-нибудь?" из очереди выходит первый нуждающийся в этом враче, или никто не выходит, если таких на данный момент нет. Время, затрачиваемое регистратурой на один вопрос, в обоих случаях одинаково.

Тривиальный принцип работы регистратуры - называть всех специалистов по кругу, но при "эпидемии" это очевидным образом неэффективно.

Требуется придумать адаптивный алгоритм, стремящийся максимизировать пропускную способность регистратуры, в т.ч. и в условиях изменения характера "эпидемий", сохраняя справедливость: стоящий первым в очереди никогда не должен ждать дольше, чем M вопросов.

Начинаем с колоды из N карточек с номерами от 1 до N. Далее играем раунды так:

Выкликаем согласно номерам на карточках, и раскладываем карточки в N пар кучек, в каждой паре справа - успешные вызовы (Si), слева - неудачные (Fi).

Когда колода исчерпалась, смотрим: если во всех N парах было хотя бы по одному успешному вызову (все Si > 0), то набор Si более или менее неплохо моделирует соотношение частот клиентов врачей, а для уточнения соотношения на следующем круге составляем колоду из 2*Si карточек каждого типа, если это не больше, чем M, иначе по Si каждого типа.

Если же оказалось, что какие-то Si равны нулю, то это значит, что частота запросов для этих i меньше, чем 1/K, где K - размер колоды на только что закончившемся круге. Тогда составляем колоду из min(M, 2*K) карточек так, чтобы в них было по одной карточке для тех i, для которых Si было = 0, а остальные были в той же пропорции, что и ненулевые Si.

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

Споласкиваем, повторяем.