时津风的资源收集【牛客tracker 每日一题】

时津风的资源收集

时间限制：1秒 空间限制：256M

知识点：广度优先搜索(BFS)

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

时津风曾沉迷于页游Kancolle。在游戏中，有一项日常任务需要玩家使用油、弹药、钢材、铝这4 44种资源来开发装备。

现给定目标资源量a , b , c , d a,b,c,da,b,c,d，时津风进入开发界面时4 44种资源均为10 1010单位。她可以对单一资源执行以下任意一种操作（资源总量始终保持在区间[ 10 , 300 ] [10,300][10,300]）：

• 将该资源± 1 ±1±1；
• 将该资源± 10 ±10±10；
• 将该资源± 100 ±100±100；
• 直接将该资源设为上限300 300300；
• 直接将该资源设为下限10 1010。

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

输入描述：

第一行输入整数T ( 1 ≦ T ≦ 10 5 ) T(1≦T≦10^5)T(1≦T≦105)—— 测试组数。
接下来T TT行，每行输入4 44个整数a , b , c , d ( 10 ≦ a , b , c , d ≦ 300 ) a,b,c,d (10≦a,b,c,d≦300)a,b,c,d(10≦a,b,c,d≦300)。

输出描述：

对每组数据输出一个整数，表示最少操作次数。

示例1

输入：

2 10 100 200 300 10 10 10 10

输出：

5 0

说明：

样例1：

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

初始[ 10 , 10 , 10 , 10 ] [10,10,10,10][10,10,10,10]
将弹药增加100 100100，变成[ 10 , 110 , 10 , 10 ] [10,110,10,10][10,110,10,10]
将弹药减少10 1010，变成[ 10 , 100 , 10 , 10 ] [10,100,10,10][10,100,10,10]
将钢材增加到上限，变成[ 10 , 100 , 300 , 10 ] [10,100,300,10][10,100,300,10]
将钢材减少100 100100，变成[ 10 , 100 , 200 , 10 ] [10,100,200,10][10,100,200,10]
将铝增加到上限，变成[ 10 , 100 , 200 , 300 ] [10,100,200,300][10,100,200,300]

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

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

解题思路

本题核心是资源独立性分解 + 单状态BFS预处理，将四维最短路问题降为一维，通过预处理实现海量查询的秒级响应。

1. 问题降维：资源独立性质
   每次操作仅针对单一资源，四种资源的调整互不影响，因此总最少操作次数等于每种资源从初始值10调整到目标值的最少操作次数之和。问题简化为：求从10出发，通过允许的操作到达数值x的最少步数，其中x ∈ [10, 300]。

2. 单资源最短路建模
   将每个资源数值视为图的节点，每个合法操作对应一条权值为1的边：

• 数值 ±1、±10、±100，若结果在 [10, 300] 范围内则构成合法转移；
• 任意数值可直接跳转至10（下限）和300（上限），各对应一步操作。
  由于所有操作步数均为1，使用BFS（广度优先搜索）可以天然求出从起点10到所有节点的最短路径。

3. 预处理 + 批量查询
   数值范围仅 10~300，共291个节点，一次BFS即可预处理出所有目标值的最少步数数组dis。对于 T 组查询，只需将四个目标值对应的dis值相加，即可 O(1) 得到每组答案，完美适配T ≤ 10^5的大数据量查询。

算法总时间复杂度：预处理为常数级，查询为 O(T)，整体效率极高。

总结

核心逻辑：利用资源独立性拆分四维问题，通过BFS预处理单资源最少操作步数，查询时直接累加四个维度的结果。
关键操作：单资源最短路建模、BFS层序遍历求最短步数、预处理数组加速批量查询。
效率保障：数值范围极小，预处理常数开销，查询O(1)，轻松应对十万级测试用例。

代码简要说明

1. 预处理函数pre：

   • 初始化距离数组dis为 -1（标记未访问），起点10的距离设为0并入队。
   • 定义6种数值加减的偏移量，遍历每个出队节点时，尝试所有加减操作，结果合法且未访问则更新距离并入队。
   • 处理直接设置上限300的操作：若300未被访问，则更新其距离为当前步数+1并入队，BFS保证首次到达即为最短路径。
   • 直接设置下限10的操作因起点就是10，最优路径不会用到回退操作，故不影响最终结果。

2. 主函数逻辑：

   • 提前调用pre完成全局预处理，仅执行一次。
   • 读取测试用例数 T，逐组读取四个目标资源值，累加对应距离后直接输出。
   • 关闭同步流加速输入输出，适配十万级查询的IO效率要求。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll dis[305];queue<ll>q;ll dx[]={1,-1,10,-10,100,-100};voidpre(){memset(dis,-1,sizeof(dis));dis[10]=0;q.push(10);while(!q.empty()){ll u=q.front();q.pop();for(ll i=0;i<6;i++){ll v=u+dx[i];if(v>=10&&v<=300&&dis[v]==-1){dis[v]=dis[u]+1;q.push(v);}}if(dis[10]==-1){dis[10]=dis[u]+1;q.push(10);}if(dis[300]==-1){dis[300]=dis[u]+1;q.push(300);}}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);pre();ll T;cin>>T;while(T--){ll a,b,c,d;cin>>a>>b>>c>>d;cout<<dis[a]+dis[b]+dis[c]+dis[d]<<'\n';}return0;}