题解 | #时津风的资源收集#

时津风的资源收集

https://www.nowcoder.com/practice/5a6f83a0e0214ba5a77f6cdc71a3027b

题目链接

时津风的资源收集

题目描述

玩家有四种资源，初始值均为 10。给定四种资源的目标量 $a, b, c, d$ 。玩家可以对任意一种资源执行以下操作，但必须保证资源量始终在 $[10, 300]$ 的区间内：

资源量 $\pm1$ 。
资源量 $\pm10$ 。
资源量 $\pm100$ 。
直接将资源量设为上限 $300$ 。
直接将资源量设为下限 $10$ 。

每种操作计为一次。求使四种资源量同时达到目标值所需的最少总操作次数。

解题思路

本题的核心是计算将四种资源从初始值 10 变为目标值所需的最少操作次数。由于对每种资源的操作是相互独立的，我们可以将问题分解为四个相同的子问题：计算单一资源从 10 变为目标值 $t$ 所需的最少操作次数。最终答案是这四个子问题解的和。

对于单一资源，问题可以抽象为一个图论中的最短路径问题。我们可以将区间 $[10, 300]$ 内的每一个整数看作图的一个节点。题目中给出的八种操作（ $\pm1, \pm10, \pm100$ , 设为 10, 设为 300）则可以看作连接这些节点的边。因为每次操作的成本都是 1，所以这是一个单位权图的最短路问题，最适合使用广度优先搜索 (BFS) 算法来解决。

预计算优化

由于题目包含多组测试数据，如果每次都对四个目标值分别运行 BFS 会非常耗时。一个高效的策略是进行预计算：在处理任何测试数据之前，先运行一次 BFS，计算出从初始值 10 到所有可能的目标值（10 到 300）的最短操作次数，并将结果存储起来。之后对于每组查询，我们只需直接查表即可，时间复杂度为 $\mathcal{O}(1)$ 。

BFS 算法流程

初始化：
- 创建一个距离数组 dist[301]，用于存储从起点 10 到达各数值所需的最少操作次数。将所有元素初始化为 -1，表示尚未访问。
- 创建一个队列，并将起点 10 入队。
- 设定 dist[10] = 0。
BFS 搜索：
- 当队列不为空时，从队首取出一个数值 $u$ 。
- 从当前值 $u$ 出发，有 8 种可能的目标状态 $v$ ： $u+1, u-1, u+10, u-10, u+100, u-100$ , 以及直接设置为 $10$ 和 $300$ 。
- 对于每一种可能的目标状态 $v$ ，检查它是否在 $[10, 300]$ 的合法范围内。如果合法且 dist[v] 为 -1（即未访问过），则更新 dist[v] = dist[u] + 1，并将 $v$ 加入队列。
查询：
- BFS 结束后，dist 数组就包含了从 10 到达任意合法数值的最短操作次数。
- 对于每组测试数据的四个目标值 $a, b, c, d$ ，总次数即为 dist[a] + dist[b] + dist[c] + dist[d]。

这种“一次预计算，多次查询”的模式是解决此类多组输入最短路问题的经典方法。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MIN_RES = 10;
const int MAX_RES = 300;
vector<int> dist(MAX_RES + 1, -1);

void precompute_bfs() {
    queue<int> q;

    dist[MIN_RES] = 0;
    q.push(MIN_RES);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        int potential_moves[] = {
            u + 1, u - 1,
            u + 10, u - 10,
            u + 100, u - 100,
            MIN_RES, MAX_RES
        };

        for (int v : potential_moves) {
            if (v >= MIN_RES && v <= MAX_RES && dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    precompute_bfs();

    int t;
    cin >> t;
    while (t--) {
        long long total_ops = 0;
        for (int i = 0; i < 4; ++i) {
            int target;
            cin >> target;
            total_ops += dist[target];
        }
        cout << total_ops << endl;
    }

    return 0;
}

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;

public class Main {
    static final int MIN_RES = 10;
    static final int MAX_RES = 300;
    static int[] dist = new int[MAX_RES + 1];

    static void precomputeBfs() {
        Arrays.fill(dist, -1);
        Queue<Integer> q = new LinkedList<>();

        dist[MIN_RES] = 0;
        q.offer(MIN_RES);

        while (!q.isEmpty()) {
            int u = q.poll();

            int[] potentialMoves = {
                u + 1, u - 1,
                u + 10, u - 10,
                u + 100, u - 100,
                MIN_RES, MAX_RES
            };
            
            for (int v : potentialMoves) {
                if (v >= MIN_RES && v <= MAX_RES && dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.offer(v);
                }
            }
        }
    }

    public static void main(String[] args) {
        precomputeBfs();
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            long totalOps = 0;
            for (int i = 0; i < 4; i++) {
                int target = sc.nextInt();
                totalOps += dist[target];
            }
            System.out.println(totalOps);
        }
    }
}

import sys
from collections import deque

MIN_RES = 10
MAX_RES = 300
dist = [-1] * (MAX_RES + 1)

def precompute_bfs():
    q = deque([MIN_RES])
    dist[MIN_RES] = 0
    
    while q:
        u = q.popleft()

        potential_moves = [
            u + 1, u - 1,
            u + 10, u - 10,
            u + 100, u - 100,
            MIN_RES, MAX_RES
        ]

        for v in potential_moves:
            if MIN_RES <= v <= MAX_RES and dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)

def solve():
    precompute_bfs()
    
    # 使用快读模板处理输入
    _input = iter(sys.stdin.read().split())
    
    # 第一个数字是测试用例数T
    t_cases = int(next(_input))
    
    for _ in range(t_cases):
        total_ops = 0
        for i in range(4):
            target = int(next(_input))
            total_ops += dist[target]
        print(total_ops)

solve()

算法及复杂度

算法：广度优先搜索 (BFS)
时间复杂度： $\mathcal{O}(MAX\_RES + T)$ 。
- 预计算的 BFS 复杂度为 $\mathcal{O}(V+E)$ ，其中 $V$ 是节点数（ $MAX\_RES - MIN\_RES + 1$ ）， $E$ 是边数。每个节点最多有 8 条出边，所以 $E$ 与 $V$ 是同阶的，复杂度为 $\mathcal{O}(MAX\_RES)$ 。
- 对于 $T$ 组测试数据，每次查询是 $\mathcal{O}(1)$ 的查表操作。
- 因此，总时间复杂度由预计算主导，为 $\mathcal{O}(MAX\_RES)$ 。
空间复杂度： $\mathcal{O}(MAX\_RES)$ 。
- 主要空间开销来自于存储所有距离的 dist 数组，以及 BFS 使用的队列。