Python程序：找出跑酷运动员所能到达的最远建筑物

假设有n栋不同高度的房屋，一位跑酷运动员想要借助砖块和梯子从一栋房屋移动到另一栋房屋。房屋的高度以数组的形式给出。每个砖块的高度为一个单位长度，我们有少量砖块。我们只能使用一次梯子和砖块。我们必须找出跑酷运动员所能到达的最远建筑物。

因此，如果输入类似于heights = [5, 8, 7, 6, 2, 3, 1, 4]，bricks = 3，ladders = 2，则输出将为7。

运动员从建筑物0开始。

他借助3块砖块到达建筑物1。

由于后续建筑物比之前的建筑物矮，他跳到建筑物2、3、4。

他使用梯子从建筑物4到达建筑物5。

由于建筑物6比建筑物5矮，他从建筑物5跳到建筑物6。

他使用最后一个梯子到达建筑物7。

为了解决这个问题，我们将遵循以下步骤：

  • temp := 新建一个堆

  • for i in range 1 to size of heights, do

    • dist := heights[i] - heights[i - 1]

    • if dist > 0, then

      • bricks := bricks - dist

      • 将值 -dist 推入堆temp

      • if bricks < 0, then

        • ladders := ladders - 1

        • bricks := bricks - 从堆temp中移除的最小元素

        • if bricks < 0 or ladders < 0, then

          • return i - 1

  • return size of heights - 1

示例

让我们看看下面的实现，以便更好地理解：

from heapq import heappush, heappop
def solve(heights, bricks, ladders):
   temp = []
   for i in range(1, len(heights)):
      dist = heights[i] - heights[i - 1]
      if dist > 0:
         bricks -= dist
         heappush(temp, -dist)
         if bricks < 0:
            ladders -= 1
            bricks -= heappop(temp)
            if bricks < 0 or ladders < 0:
               return i - 1
   return len(heights) - 1

print(solve([5, 8, 7, 6, 2, 3, 1, 4], 3, 2))

输入

[5, 8, 7, 6, 2, 3, 1, 4], 3, 2

输出

7

更新于：2021年10月6日

浏览量：134

开启你的职业生涯

通过完成课程获得认证

开始学习
广告