Алгоритм минимизации максимального продукта (конфеты и шарики)

Question

Здравствуйте, мне нужна помощь по следующей проблеме:
у нас есть m воздушных шаров и неограниченное количество конфет.
Какой-то ребенок хочет, чтобы мы давали ему ni воздушных шаров в каждый i день (массив * 1006)*).
У него также есть массив налогов b - который является налогом bi в день i.
Если мы дадим ребенку ni воздушных шаров в день i, он будет счастлив. Если мы даем k воздушных шаров k < ni в день i, мы должны дать ребенку (ni - k)*bi конфеты.
Мы должны давать воздушные шары таким образом, чтобы минимизировать максимальное количество конфет, которые мы даем наДАННЫЙ ДЕНЬ.
Пример:
у нас есть 6 шары (m = 6)

n = 1, 3, 3, 3, 2  
b = 4, 1, 5, 3, 7  

мы даем шары следующим образом

g = 0, 0, 2, 2, 2  

Таким образом, мы имеемчтобы дать максимум (3 -2) * 5 = 5 в день 3 (индексирование начинается с 1).

Пожалуйста, помогите мне найти эффективное решение этой проблемы. Мое текущее решение жадно, удаляя один шарик за раз, но слишком медленно, потому что m < 10^18. ai < 10^9 bi < 10^9 n < 10^5

Answer 1

Один из подходов состоит в достижении минимума максимального ежедневного налога с помощью бинарного поиска.

Предположим, что максимальный ежедневный налог будет равен T_current (половина от 0 до максимально возможного ежедневного налога для первогоитерация). Найдите необходимое количество воздушных шаров на каждый день, чтобы они не превышали T_current. Сумма всех таких шаров составляет M_current. Если M_current больше, чем ввод M, то для следующей итерации предполагается, что T_current больше, а если для следующей итерации меньше, чем T_current.

В каждой итерации вы сокращаете область поиска. за T пополам. Вы продолжаете двоичный поиск, чтобы найти T_current такой, что M_current == M. Если у вас есть T_current, у вас также есть раздача воздушных шаров.