时津风的资源收集
时间限制：1秒 空间限制：256M
知识点：广度优先搜索(BFS)
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！ 
题目描述
时津风曾沉迷于页游 Kancolle。在游戏中，有一项日常任务需要玩家使用油、弹药、钢材、铝这
4
4
4 种资源来开发装备。
现给定目标资源量
a
,
b
,
c
,
d
a,b,c,d
a,b,c,d ，时津风进入开发界面时
4
4
4 种资源均为
10
10
10 单位。她可以对单一资源执行以下任意一种操作（资源总量始终保持在区间
[
10
,
300
]
[10,300]
[10,300] ）：
- 将该资源
±
1
±1
±1 ； - 将该资源
±
10
±10
±10 ； - 将该资源
±
100
±100
±100 ； - 直接将该资源设为上限
300
300
300 ； - 直接将该资源设为下限
10
10
10 。
在保证所有资源始终处于合法范围的前提下，求使四种资源同时恰好达到
(
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
T
T 行，每行输入
4
4
4 个整数
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
100
100 ，变成
[
10
,
110
,
10
,
10
]
[10,110,10,10]
[10,110,10,10] 将弹药减少
10
10
10 ，变成
[
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
100
100 ，变成
[
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
5
5 次以下的操作来达到开发所需的资源量，所以答案为
5
5
5 。
第二组测试数据，开发所需的资源量就为资源初始值，所以不需要进行任何操作。
解题思路
本题核心是资源独立性分解 + 单状态BFS预处理，将四维最短路问题降为一维，通过预处理实现海量查询的秒级响应。
问题降维：资源独立性质 每次操作仅针对单一资源，四种资源的调整互不影响，因此总最少操作次数等于每种资源从初始值10调整到目标值的最少操作次数之和。问题简化为：求从10出发，通过允许的操作到达数值 x 的最少步数，其中 x ∈ [10, 300]。
单资源最短路建模 将每个资源数值视为图的节点，每个合法操作对应一条权值为1的边：
- 数值 ±1、±10、±100，若结果在 [10, 300] 范围内则构成合法转移；
- 任意数值可直接跳转至10（下限）和300（上限），各对应一步操作。 由于所有操作步数均为1，使用BFS（广度优先搜索）可以天然求出从起点10到所有节点的最短路径。
算法总时间复杂度：预处理为常数级，查询为 O(T)，整体效率极高。
总结
核心逻辑：利用资源独立性拆分四维问题，通过BFS预处理单资源最少操作步数，查询时直接累加四个维度的结果。 关键操作：单资源最短路建模、BFS层序遍历求最短步数、预处理数组加速批量查询。 效率保障：数值范围极小，预处理常数开销，查询O(1)，轻松应对十万级测试用例。
代码简要说明
预处理函数 pre：
- 初始化距离数组 dis 为 -1（标记未访问），起点10的距离设为0并入队。
- 定义6种数值加减的偏移量，遍历每个出队节点时，尝试所有加减操作，结果合法且未访问则更新距离并入队。
- 处理直接设置上限300的操作：若300未被访问，则更新其距离为当前步数+1并入队，BFS保证首次到达即为最短路径。
- 直接设置下限10的操作因起点就是10，最优路径不会用到回退操作，故不影响最终结果。
主函数逻辑：
- 提前调用 pre 完成全局预处理，仅执行一次。
- 读取测试用例数 T，逐组读取四个目标资源值，累加对应距离后直接输出。
- 关闭同步流加速输入输出，适配十万级查询的IO效率要求。
代码内容
#include <bits/stdc++.h>
using namespace std;
#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;
ll dis[305];
queue<ll> q;
ll dx[]={1,–1,10,–10,100,–100};
void pre()
{
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);
}
}
}
int main()
{
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';
}
return 0;
}
