最小化最大产品（糖果和气球）的算法
Algorithm for minimizing maximium product (candy and ballons)
您好，我需要帮助解决以下问题：
我们有m个气球和无限量的糖果。
有些孩子希望我们每 i 天给他 ni 个气球（数组 n）。
他还有一个税收数组 b - 这是 i 日的税收 bi。
如果我们在 i 那天给孩子 ni 个气球，他会很高兴。如果我们在 i 天给 k 个气球 k < ni，我们就得给孩子 (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 天（索引从 1 开始）给出最大值 (3 -2) * 5 = 5。
请帮我找到解决这个问题的有效方法。我目前的解决方案是贪婪的，一次移除一个气球，但速度太慢，因为 m < 10^18。 ai < 10^9 bi < 10^9 n < 10^5
一种方法是通过二分查找达到最高每日税收的最小值。
假设最大每日税收为 T_current（第一次迭代中介于 0 和最大可能每日税收之间的一半）。找出每天所需的气球数量，使其不超过 T_current。所有这些气球的总和是 M_current。如果 M_current 大于输入 M，则下一次迭代假设更大的 T_current，如果小于，则下一次迭代假设更小的 T_current。
在每次迭代中，您将 T 的搜索域减半。您继续二进制搜索以找到 T_current 使得 M_current == M。一旦你有了这个T_current你也有气球的分布。
您好，我需要帮助解决以下问题：
我们有m个气球和无限量的糖果。
有些孩子希望我们每 i 天给他 ni 个气球（数组 n）。
他还有一个税收数组 b - 这是 i 日的税收 bi。
如果我们在 i 那天给孩子 ni 个气球，他会很高兴。如果我们在 i 天给 k 个气球 k < ni，我们就得给孩子 (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 天（索引从 1 开始）给出最大值 (3 -2) * 5 = 5。
请帮我找到解决这个问题的有效方法。我目前的解决方案是贪婪的，一次移除一个气球，但速度太慢，因为 m < 10^18。 ai < 10^9 bi < 10^9 n < 10^5
一种方法是通过二分查找达到最高每日税收的最小值。
假设最大每日税收为 T_current（第一次迭代中介于 0 和最大可能每日税收之间的一半）。找出每天所需的气球数量，使其不超过 T_current。所有这些气球的总和是 M_current。如果 M_current 大于输入 M，则下一次迭代假设更大的 T_current，如果小于，则下一次迭代假设更小的 T_current。
在每次迭代中，您将 T 的搜索域减半。您继续二进制搜索以找到 T_current 使得 M_current == M。一旦你有了这个T_current你也有气球的分布。