最小化最大乘积的算法（糖果和气球）

Question

你好，我需要帮助解决以下问题：
我们有 m 个气球和无限数量的糖果。
一个孩子想在每一天中得到 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  

我们需要在第三天（从1开始索引）给予最大值5，计算方法是(3-2)*5=5。

请帮我找到一个高效的解决方案。目前我的贪心算法是每次移除一个气球，但速度太慢了，因为m < 10^18。ai < 10^9 bi < 10^9 n < 10^5

- Teodor Dyakov

---

也许逐个删除是可以的，但你必须拥有按天分类的已排序税金列表，并在每次删除后更新它，并始终从列表中的第一项中删除气球。此外，如果 m 接近于 ni 的总和，则从相反方向开始添加税金而不是删除可能更有效。 - Dialecticus

@גלעדברקן ai < 10^9 和 bi < 10^9 - Teodor Dyakov

@Dialecticus 我试过了，但会因为 m < 10^18 而超时。 - Teodor Dyakov

Answer 1

一种方法是使用二分查找来达到每日最大税收的最小值。

假设每日最大税收为T_current（介于0和第一次迭代可能的最大每日税收之间的一半）。找出每天所需的气球数量，使其不超过T_current。所有这样的气球的总数为M_current。如果M_current大于输入的M，则下一次迭代假设更大的T_current，如果M_current小于输入的M，则下一次迭代假设更小的T_current。

在每次迭代中，将用于T的搜索区域缩小一半。您继续进行二分查找，以找到T_current，使M_current == M。一旦获得了此T_current，您还将获得气球的分布。

- Dialecticus