最小化最大产品(糖果和气球)的算法

Question

您好，我需要帮助解决以下问题:
我们有m气球和无限量的糖果。
有些 child 要我们给他 ni每个i中的气球天(数组 n )。
他还有一个税阵b - 这是税bi当天i .
如果我们给 child ni当天的气球i他很高兴。如果我们给k气球k < ni当天i ，我们要给 child (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，你也有气球的分布。