Алгоритм простой, подготовка O(n), расчёт O(log n). Вычислить функцию распределения (она кусочно-постоянная). Сгенерировать равномерно распределённое число, определить, в какой кусок оно попадает.
Для целых «шансов» — если сумма этих «шансов» 123, то генерируем число от 0 до 122, а дальше понятно.
Алгоритм многопамятный, подготовка O(sum a
i), расчёт O(1). Годится только для небольших целых шансов.
Его предложил
Сергей Соколов.
Алгоритм палочный, подготовка O(n log n), расчёт O(1).
https://elementy.ru/problems/2263/Razdelyay_i_uravnivay
Алгоритм легко переделывается на ситуацию, когда все палки имеют целую длину, резать-клеить их можно только по целым длинам, при этом последняя палка может оказаться короче. В общем, простым делением определяем, в какую палку попали, а потом доступом к массиву и сравнением — в какой компонент данной палки.
Например, у нас есть четыре шанса — 100, 20, 2 и 1. Палочный алгоритм даст, например, такие палки (у всех длина 31, и у последней — 30).
Палка [0..31): 1 (x<1); 100 (x>=1)
Палка [31..62): 2 (x<33); 100 (x>=33)
Палка [62..93): 20 (x<82); 100 (x>=82)
Палка [93..123): всегда 100
Разыграв 32, получаем: [32/31] = 1, первая палка. 32<33 — та шмотка, у которой два шанса.
