火车站有n个售票窗口。第j个窗口有a(j)张票可用。一张票的价格等于该窗口此时剩余的票数。火车站卖出前m张票最多可以赚取多少钱?
例如,如果我们有三个售票窗口,它们的票数分别为3、3和4,我们想要卖出5张票。这时:
n = 3, m = 5
A[3] = {3, 3, 4}
最大的赚钱数是4 + 3 + 3 + 3 + 2 = 15。
我在网上看到这个问题,我的解决方案是先将所有的票号推入最大堆中,然后运行一个for循环m次。每次我们弹出最大堆的顶部值,并将其添加到总赚钱数中,如果该值大于1,我们将(value - 1)推入最大堆中。
但是这种方法有点耗时,有更好的解决方案吗?