最大收益算法

Question

如何计算n个售票窗口的m门票所赚取的最高金额,票价与票房的票数相等？

火车站有n个售票窗口.带窗口的(j)门票可用.票价与当时该窗口中剩余的票数相等.卖火车票的最高金额是多少？

例如,如果我们有3个售票窗口,有3个,3个,4个门票,我们想卖5张门票.然后:

n = 3, m = 5
A[3] = {3, 3, 4}

赚取的最高金额是4 + 3 + 3 + 3 + 2 = 15

我在网上看到了这个问题,我的解决方案是首先将所有票号都推到maxHeap并运行for循环m次.每次我们弹出maxHeap的最高值并将其添加到所赚取的总金额中,如果该值大于1,我们将(value - 1)推送到maxHeap.

但这在某种程度上耗费时间消耗任何更好的解决方案？

Answer 1

为了解决这个问题，我们需要做一个观察：

• 为了获得最大的结果，我们需要获得最多的m票。

设x为一个窗口中剩余的最大门票数量，因此一个窗口i对总收入的贡献为

(a(i) + a(i) - 1 + ... + x + 1) = a(i)*(a(i) + 1)/2 - x*(x + 1)/2

为了找到x，我们可以使用二分查找

int start = 0;
int end = maximum number of ticket in one window;
while(start <= end)
   int mid = (start + end)/2;
   for(each window)
      number of sell ticket += a(i) - mid;//if mid is larger than a(i), just add a zero
   if(number of sell ticket >= m)
      increase start;
   else
      decrease end;

因此，时间复杂度为 O(n log m)，其中 n 是窗口数量，m 是一个窗口中的最大票数。