首页 > 试题广场 >

时津风的资源收集

[编程题]时津风的资源收集
  • 热度指数：1366 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
{\hspace{15pt}}时津风曾沉迷于页游 Kancolle。在游戏中，有一项日常任务需要玩家使用油、弹药、钢材、铝这 4 种资源来开发装备。
{\hspace{15pt}}现给定目标资源量 a,b,c,d，时津风进入开发界面时 4 种资源均为 10 单位。她可以对单一资源执行以下任意一种操作（资源总量始终保持在区间 [10,300]）：
{\hspace{23pt}}\bullet\,将该资源 \pm 1；
{\hspace{23pt}}\bullet\,将该资源 \pm 10；
{\hspace{23pt}}\bullet\,将该资源 \pm 100；
{\hspace{23pt}}\bullet\,直接将该资源设为上限 300；
{\hspace{23pt}}\bullet\,直接将该资源设为下限 10。

{\hspace{15pt}}在保证所有资源始终处于合法范围的前提下，求使四种资源同时恰好达到 (a,b,c,d) 所需的最少操作次数。

输入描述:
{\hspace{15pt}}第一行输入整数 T\left(1\leqq T\leqq 10^{5}\right) —— 测试组数。
{\hspace{15pt}}接下来 T 行，每行输入 4 个整数 a,b,c,d\ \left(10\leqq a,b,c,d\leqq 300\right)。


输出描述:
{\hspace{15pt}}对每组数据输出一个整数，表示最少操作次数。
示例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。

第二组测试数据，开发所需的资源量就为资源初始值，所以不需要进行任何操作。
算法知识视频讲解
添加回答
Python3
卡卡喵头像 卡卡喵 
import sys

for line in sys.stdin:
    data = line.split()
    n = int(data[0])
    break

dp = [float("inf") for _ in range(301)]
dp[10] = 0
dp[300] = 1
operation = [1, -1, 10, -10, 100, -100]
count = 0
while float("inf") in dp:
    for i in range(301):
        if dp[i] == count:
            for op in operation:
                x = i + op
                if 0 <= x <= 300 and dp[x] == float("inf"):
                    dp[x] = count + 1
    count += 1

for line in sys.stdin:
    data = line.split()
    data = [int(x) for x in data]
    print(sum(dp[num] for num in data))

发表于 2026-03-12 22:23:31 回复(0)
提交观点

问题信息

广度优先搜索(BFS)
来自：华为机试编程模拟题6
难度：
1条回答 942浏览

热门推荐

相关试题

时津风的资源收集

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号