algorithm - 使用优先队列的出租车算法

Question

出租车号码是一个可以表示为两个立方体之和的数字，以两种不同的方式表示，其中整数 a、b、c、d 不相等。以下代码使用优先级队列生成此类数字。

for i = 1..n
   pq.insert( Vector(i^3+i^3,i,i) )

  prev = Vector(0, 0, 0)
  while not pq.empty()
     curr = pq.deleteMin()
     if prev[0] == curr[0]
        print curr[0] is a Taxicab number that can be expressed as
        prev[1]^3 + prev[2]^3 and curr[1]^3 + curr[2]^3
     prev = curr
     if curr[2] < N
        j = curr[2] + 1
        pq.insert( Vector(curr[1]^3+ j^3, curr[1], j) )

其中一个数字是:1729 = 12^3 + 1^3 = 10^3 + 9^3。prev = [1729, 12, 1] 和 current = [1729, 10, 9] 如果 while 循环的每次迭代，唯一优先级队列中的 (top ie.min) 元素被删除并且 prev 等于之前迭代的数字，所以对于这个例子它将是 [1512, 10, 8] (因为 while 循环只修改第一个和第三个元素)。

Answer 1

答案是，当您将一个元素插入优先级队列时，它自然会下降到其第一个元素指定的级别。因此，您可以按照您认为的任何顺序插入元素，然后按总和顺序将它们拉出。只要您随后插入的东西的总和大于您取出的东西，即使您不是从其中的所有东西开始，您也会以正确的顺序取出所有东西。