京东 · 广度优先搜索(BFS) · 算法编程题
京东 广度优先搜索(BFS) 时限 1 秒 / 256 MB

题目描述

给出两个正整数 a, b ，每次可以选择其中一个数字，然后将其替换为 a,b 的几何平均数或者 a,b 的平方平均数。问最少经过几次替换，可以使得 a,b 两个数相等。
注：
几何平均数： √(a × b)
平方平均数： √((a^2+b^2/2))
题目计算过程中几何平均数上取整，平方平均数下取整

输入输出

输入描述
在一行中给出两个正整数 a,b
1 ≤ a ≤ b ≤ 2000
输出描述
在一行中输出一个非负整数表示最少的替换次数

样例共 2 组

样例 1 · 将 2 替换成 ⌈ √(2 × 4) ⌉ = 3 ，然后将 4 替换成 ⌊ √((3^2+4^2/2)) ⌋ = 3
输入
2 4
输出
2
样例 2 · 将 12 替换为 ⌊ √((12^2+16^2/2)) ⌋ = 14 ，然后将 16 替换成 ⌈ √(14 × 16)⌉ = 15 ，最后将 14 替换为 ⌈ √(14 × 15)⌉ = 15
输入
12 16
输出
3

算法解析依据充分

考点：广度优先搜索(BFS) · 基础数学

限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 元素值域：a ≤ 2000，b ≤ 2000（注意整数类型选择，避免溢出）
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：广度优先搜索(BFS)

按层扩散搜索，无权图上第一次到达即最短路。

思路框架（广度优先搜索(BFS) 通法 · 非本题专属）

  1. 起点入队并标记已访问。
  2. 每次取队首，把它的所有未访问邻居入队并记录步数。
  3. 第一次访问到目标时，步数即为最少步数。
  4. 网格类题目通常有 4（或 8）个方向，用方向数组统一处理。

实现要点：标记访问必须在入队时做，不能在出队时做，否则会重复入队甚至超时。

复杂度：时间 O(V+E) ｜ 空间 O(V)

该范式的通法易错点

  • 出队才标记访问导致 MLE/TLE。
  • 网格边界没判，越界访问。
  • 多源 BFS 时只把第一个起点入队。

对照本题

  • 元素值域最大到 2000 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 2 4 → 输出 2

将 2 替换成 ⌈ √(2 × 4) ⌉ = 3 ，然后将 4 替换成 ⌊ √((3^2+4^2/2)) ⌋ = 3

样例 2：输入 12 16 → 输出 3

将 12 替换为 ⌊ √((12^2+16^2/2)) ⌋ = 14 ，然后将 16 替换成 ⌈ √(14 × 16)⌉ = 15 ，最后将 14 替换为 ⌈ √(14 × 15)⌉ = 15

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2024年春招-京东-技术通用岗位-第三批笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解