你好,我需要帮助解决以下问题:
我们有 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
m
接近于ni
的总和,则从相反方向开始添加税金而不是删除可能更有效。 - Dialecticus