Идея решения задачи олимпиадного программирования
Есть n дробей вида ai/bi (1 <= n <= 5000, 1 <= ai, bi <= 1000000, ai, bi - натуральные). Требуется выбрать из них 1<=k<=n дробей таким образом, чтобы дробь, числитель которой равен сумме числителей этих дробей, а знаменатель равен сумме знаменателей дробей, была максимальной. Ограничение по времени 2 секунды, по памяти 256 МБайт.
Например, n=2, k=2, a0=1, b0=5, a1=2, b1=3. Здесь берутся все дроби, а результат равен (1+2)/(5+3)=3/8.
Возможный подход - динамическое программирование - пытался рассуждать в сторону вычисления dp[nUsed][nViewed] - максимального значения дроби, где nUsed - число дробей, входящих в нее, а nViewed - число просмотренных дробей. Тогда ответ будет в dp[k][n]. Но я не знаю, как этот подход улучшить, он не пройдет ни по памяти (чтобы просто хранить 25 млн значений dp, требуется 25*10^6 * 2 * sizeof(int64), ибо максимальное значение числителя и знаменателя итоговой дроби может превышать uint32), ни по времени (тут зависит от числа переходов между элементами - может, можно делать восходящую динамику и делать лишь пару переходов - из значения dp[nUsed][nViewed] обновлять значение dp[nUsed+1][nViewed+1] или dp[nUsed][nViewed+1]).
Еще пытался думать в сторону жадности. Каким-то образом отсортировать (например, по значению дробей), затем набрать k первых дробей. После этого просмотреть оставшиеся n-k дробей и смотреть, можно ли заменить какую-то из добавленных ранее дробей новой дробью, что результат улучшится.
Ответы (1 шт):
Задача решается с помощью бинарного поиска по ответу.
На каждой итерации бинарного поиска проверяем, существует ли набор из k дробей ai/bi, что (a1+a2+...+ak)/(b1+b2+...+bk) >= x. Если существует, то ответ как минимум x, иначе ответ строго меньше x.
Далее можно рассмотреть неравенство:
(a1+a2+...+ak)/(b1+b2+...+bk) >= x.
Поскольку (b1+b2+...+bk) > 0, то умножение обеих частей неравенства на эту скобку не приведет к смене знака неравенства:
(a1+a2+...+ak) >= x*(b1+b2+...+bk).
Далее раскроем скобки, перенесем все слагаемые влево и сгруппируем подобным образом:
(a1-x*b1)+(a2-x*b2)+...+(ak-x*bk) >= 0.
Далее отсортируем все пары значений (ai, bi) по убыванию ключа ai-x*bi и найдем сумму первых k значений ai-x*bi. Если эта сумма меньше 0, то нельзя выбрать k пар (ai, bi) для выполнения неравенства, иначе можно.
На каждой итерации алгоритма поддерживается полуинтервал бинарного поиска [left; right). Бинарный поиск завершается, когда достигается требуемая точность eps, то есть выполняется условие left + eps >= right. В качестве начального значения для left можно выбрать 0, потому что любой набор из k дробей даст значение, строго большее 0, из условия натуральности ai и bi. В качестве начального значения для right можно взять, например, 10^6+1 - чуть больше, чем максимальное достижимое значение 10^6 = (k * 10^6) / (k * 1).