Пусть есть Q единиц товара. Есть k точек, по которым необходимо распределить товар. При этом точка i может принять не более qi товара. Также заданы пропорции p1, ..pk, по которым необходимо распределить товар. То есть, если нет ограничения qi, то точка i получает (pi * Q)/(p1 + ...+pk) товара(забудем на время об округлении).
Алгоритм распределения товара таков:
- Найдем одну из точек таких, что qi <= (pi * Q)/(p1 + ... + pk). Тогда положим точке i товара qi и вычеркнем ее из дальнейшей работы (положим k = k -1, Q = Q — qi, удалим qi и pi).
- Продолжаем шаг 1 до тех пор, пока не перестанем находить такую точку.
- Каждой из оставшихся точек положим (pi * Q)/(p1 + ... + pk) товара.
- *. На самом деле в пункте 3 есть проблема с округлением, которую я опустил. Реально же алгоритм может выглядеть так. Положим m = Q mod k. Отсортируем точки по qi. И первые k - m точек получат [(pi * Q) /(p1 + ... + pk)], оставшиеся же ](pi * Q) / (p1 + ... + pk)[. Где [] - округление вниз, а ][ - вверх.
Если реализовывать такой алгоритм, то шаг 1 может повториться k раз (например у точек большой излишек товара). Тогда итоговая сложность такого алгоритма O(k^2).
Можно придумать эквивалентный алгоритм со сложностью O(k * logk). А именно, отсортируем все точки по отношению qi / pi.
Тогда, все точки, которые мы находили на шаге 1, фактически окажутся в начале. И алгоритм привратиться в следующий:
- Пока qi <= (pi * Q) / (p1 + ... + pk) , аналогично первому шагу пред. алгоритма полагаем товара qi...
- .Для оставшихся точек выполняем пункт 3*.
Во-первых, несколько слов о корректности исходного алгоритма.
Верно следующее утверждение.
Если точка j подходит под вычеркивание, а вычеркнута точка i, то после этого точка j все равно подходит.
Докажу.
Не умаляя общности пусть i = 1, а j = 2.
Фактически дано q1 <= Q * p1 / P(можем выбрать точку 1), и q2 <= Q * p2 / P (можем выбрать точку 2), надо доказать, что q2 <= p2 * (Q - q1) / (P - p1) (т.е. , что можем выбрать точку 2, после того, как выбрали точку 1).
Действительно, покажем, что Q*p2 / P <= p2 * (Q - q1) / (P - p1). После преобразований получается P * Q - Q * p1 - P * Q + P * q1 = P * q1 - Q * p1 <= 0 (из первого нер-ва).
Утверждение говорит, распределение товара не зависит от того, в каком порядке выбираются точки в пункте 1.
Также верно следующее утверждение.
Пусть точки упорядочены по qi/pi. Тогда если точка i+1 может быть вычеркнута, то и точка i также может быть вычеркнута. Не ограничивая общности, положим i равной 1, а P = p1 + ... pk.
Докажу это простенькое утверждение.
Фактически, дано q1/p1 <= q2/p2 (условие упорядоченности) и q2 <= (p2 * Q) / P (можем вычеркнуть точку 2).
Необходимо показать, что q1 <= (p1 * Q ) / P, то есть что можем вычеркнуть и точку 1.
- q1 <= q2 * p1 / p2.
- q1 <= (p1 * p2 * Q) /(P * p2).
То есть q1 <= (p1 * Q) / P, что доказать и требовалось.
Еще нужно итоговое утверждение об одиноковости вычеркнутых точек.
Утверждение.
Из последнего утверждения и следует эквивалентность алгоритмов.
Интересно, что решение очень простое, а анализ и доказательство заставляют немного подумать.:). Аналитики местные говорили, что пользователи не понимают сложных алгоритмов. И я её когда-то сделал на интуиции(то есть не доказал, но почти понял, что это так).
