用 Python 编写程序，通过小步和大步找到到达目的地所需的最佳步数

pythonserver side programmingprogramming更新于 2025/12/17 17:16:17

假设我们有一个查询列表 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) 的上限
从 main 方法中，执行以下操作 −
res := a new list
对于 Q 中的每个 q，执行
- (a, b, d) := q
- 在 res 末尾插入步骤 (a, b, d) 的结果
返回 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))