首页 > 试题广场 >

时津风的资源收集

[编程题]时津风的资源收集
  • 热度指数：287 时间限制：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。

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

import (
	"fmt"
)

type Node struct{
    value, step int
}

var result [301]int // 存储10到其他数值所需的操作次数
func BFS() { // 计算10到其他数值所需的操作次数
    for i:=0;i<=300;i++{
        result[i] = -1
    }
    queue := []Node{{10,0}}
    result[10]=0
    var cur Node
    var dist []int
    for len(queue) > 0{
        cur = queue[0]
        queue = queue[1:]

        dist = []int{
            cur.value-1,cur.value+1,
            cur.value+100,cur.value-100,
            cur.value+10, cur.value-10,
            10, 300,
        }
       
        for _, d := range dist {
            if d < 10 || d >300 || result[d] != -1{
                continue
            }
            result[d] = cur.step + 1
            queue = append(queue, Node{d, cur.step+1})
        }
    }
}

func main() {
    var a, b, c, d int
    var t int
    fmt.Scanf("%d", &t)
    BFS()
    for t >0 {
        t--
        fmt.Scanf("%d %d %d %d", &a, &b, &c, &d)
        
        fmt.Println(result[a]+result[b]+result[c]+result[d])
    }
}

发表于 2025-09-07 16:13:03 回复(0)
提交观点

问题信息

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

热门推荐

相关试题

时津风的资源收集

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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