Python程序：计算婴儿步和巨人步到达目的地的最优步数

假设我们有一系列查询Q，每个查询Q[i]包含一个三元组[a_i, b_i和d_i]。考虑我们最初位于(0, 0)位置，那么一步内我们可以从某个位置(x1, y1)移动到(x2, y2)，这两个点之间的欧几里得距离至少为a，最多为b。现在对于每个查询，我们必须找到从(0, 0)到达(d_i, 0)所需的最小步数。

因此，如果输入类似于Q = [(2,3,1), (1,2,0), (3,4,11)]，则输出将为[2, 0, 3]，因为对于第一个查询，从(0, 0)出发，a = 2，我们可以先移动到$\left(\frac{1}{2},\frac{\sqrt{15}}{2}\right)$，然后到(1, 0)，所以我们需要两步，因此输出为2；对于下一个查询，d为0，所以我们不需要移动任何步，因此输出为0；对于第三个查询，b = 4，a = 3，从(0, 0)移动到(4, 0)，然后到(8, 0)，最后到(11, 0)。

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

  • 定义一个函数steps()。它将接收a、b、d作为参数。
  • mmin := a和b的最小值
  • mmax := a和b的最大值
  • 如果d为0，则
    • 返回0
  • 如果d等于mmin或mmax，则
    • 返回1
  • 如果d < mmax，则
    • 返回2
  • 返回(d / mmax)的上取整
  • 在主方法中，执行以下操作：
  • res := 新建一个列表
  • 对Q中的每个q执行以下操作：
    • (a, b, d) := q
    • 将steps(a, b, d)的结果插入到res的末尾
  • 返回res

示例

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

from math import ceil

def steps(a, b, d):
   mmin = min(a, b)
   mmax = max(a, b)
   if d is 0:
      return 0
   if d in [mmin, mmax]:
      return 1
   if d < mmax:
      return 2
   return ceil(d / mmax)

def solve(Q):
   res = []
   for q in Q:
      a, b, d = q
      res.append(steps(a, b, d))
   return res

Q = [(2,3,1), (1,2,0), (3,4,11)]
print(solve(Q))

输入

[(2,3,1), (1,2,0), (3,4,11)]

输出

[2, 0, 2.0]

更新于：2021年10月11日

浏览量：319

开启你的职业生涯

完成课程获得认证

开始学习
广告