华为 · 广度优先搜索(BFS) · 算法编程题
华为 广度优先搜索(BFS) T ≤ 1e5 时限 1 秒 / 256 MB

题目描述

时津风曾沉迷于页游 Kancolle。在游戏中，有一项日常任务需要玩家使用油、弹药、钢材、铝这 4 种资源来开发装备。
现给定目标资源量 a,b,c,d ，时津风进入开发界面时 4 种资源均为 10 单位。她可以对单一资源执行以下任意一种操作（资源总量始终保持在区间 [10,300] ）：
将该资源 ± 1 ；
将该资源 ± 10 ；
将该资源 ± 100 ；
直接将该资源设为上限 300 ；
直接将该资源设为下限 10 。
在保证所有资源始终处于合法范围的前提下，求使四种资源同时恰好达到 (a,b,c,d) 所需的最少操作次数。

输入输出

输入描述
第一行输入整数 T(1≤ T≤ 10^5) —— 测试组数。
接下来 T 行，每行输入 4 个整数 a,b,c,d(10≤ a,b,c,d≤ 300) 。
输出描述
对每组数据输出一个整数，表示最少操作次数。

样例共 1 组

样例 1 · 样例1： 第一组测试数据，可能的操作是： 初始 [10,10,10,10] 将弹药增加 100 ，变成 [10,110,10,10] 将弹药减少 10 ，变成 [10,100,10,10] 将钢材增加到上限，变成 [10,100,300,10] 将钢材减少 100 ，变成 [10,100,200,10] 将铝增加到上限，变成 [10,100,200,300] 可以发现无法使用 5 次以下的操作来达到开发所需的资源量，所以答案为 5 。 第二组测试数据，开发所需的资源量就为资源初始值，所以不需要进行任何操作。
输入
2
10 100 200 300
10 10 10 10
输出
5
0

算法解析依据充分

考点：广度优先搜索(BFS)

数据规模 T ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：T ≤ 1e5
  • 元素值域：a ≤ 300，b ≤ 300，c ≤ 300（注意整数类型选择，避免溢出）
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

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

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

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

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

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

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

该范式的通法易错点

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

对照本题

  • 数据规模 T ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 元素值域最大到 300 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 2 / 10 100 200 300 / 10 10 10 10 → 输出 5 / 0

样例1：

第一组测试数据，可能的操作是：

初始 [10,10,10,10]

将弹药增加 100 ，变成 [10,110,10,10]

将弹药减少 10 ，变成 [10,100,10,10]

将钢材增加到上限，变成 [10,100,300,10]

将钢材减少 100 ，变成 [10,100,200,10]

将铝增加到上限，变成 [10,100,200,300]

可以发现无法使用 5 次以下的操作来达到开发所需的资源量，所以答案为 5 。

第二组测试数据，开发所需的资源量就为资源初始值，所以不需要进行任何操作。

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

本题来源：华为机试编程模拟题6。

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