Hello I need help with the following problem:
we have m balloons and unlimited amount of candy.
Some kid wants us give him ni balloons in every i day (array n).
He also has a tax array b - which is tax bi on day i.
If we give the kid ni balloons on day i he is happy. If we give k balloons k < ni on day i, we have to give the kid (ni - k)*bi candy.
We have to give the balloons in such way as to minimize the maximum amount of candy we give ON A GIVEN day.
Example:
we have 6 balloons (m = 6)
n = 1, 3, 3, 3, 2
b = 4, 1, 5, 3, 7
we give balloons in following way
g = 0, 0, 2, 2, 2
In this way we have to give a maximum of (3 -2) * 5 = 5 on day 3 (indexing start from 1).
Please help me find an efficient solution to this problem. My current solution is greedy by removing one balloon at a time but is way too slow, because m < 10^18. ai < 10^9 bi < 10^9 n < 10^5
One approach would be to reach the minimum of the max daily tax with binary search.
Assume that the max daily tax would be T_current (half between 0 and the largest possible daily tax for the first iteration). Find the required number of balloons for each day so that they do not exceed T_current. Sum of all such balloons is M_current. If M_current is larger than input M then assume larger T_current for next iteration, and if it is smaller than assume smaller T_current for next iteration.
In each iteration you cut the search domain for T in half. You continue the binary search to find the T_current such that M_current == M. Once you have this T_current you also have the distribution of balloons.