HJ163 时津风的资源收集

题目题解(15)讨论(7)排行中等 通过率44.75% 时间限制1秒 空间限制256M知识点广度优先搜索(BFS)校招时部分企业笔试将禁止编程题跳出页面为提前适应练习时请使用在线自测而非本地IDE。描述时津风曾沉迷于页游Kancolle。在游戏中有一项日常任务需要玩家使用油、弹药、钢材、铝这 44 种资源来开发装备。现给定目标资源量 a,b,c,da,b,c,d时津风进入开发界面时 44 种资源均为 1010 单位。她可以对单一资源执行以下任意一种操作资源总量始终保持在区间 [10,300][10,300]∙ ∙将该资源 ±1±1∙ ∙将该资源 ±10±10∙ ∙将该资源 ±100±100∙ ∙直接将该资源设为上限 300300∙ ∙直接将该资源设为下限 1010。在保证所有资源始终处于合法范围的前提下求使四种资源同时恰好达到 (a,b,c,d)(a,b,c,d) 所需的最少操作次数。输入描述第一行输入整数 T(1≦T≦105)T(1≦T≦105) —— 测试组数。接下来 TT 行每行输入 44 个整数 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] 将弹药增加 100100变成 [10,110,10,10][10,110,10,10] 将弹药减少 1010变成 [10,100,10,10][10,100,10,10] 将钢材增加到上限变成 [10,100,300,10][10,100,300,10] 将钢材减少 100100变成 [10,100,200,10][10,100,200,10] 将铝增加到上限变成 [10,100,200,300][10,100,200,300] 可以发现无法使用 55 次以下的操作来达到开发所需的资源量所以答案为 55。 第二组测试数据开发所需的资源量就为资源初始值所以不需要进行任何操作。#include iostream #include vector #include queue using namespace std; const int MIN_RES 10; const int MAX_RES 300; vectorint dist(MAX_RES 1, -1); void precompute_bfs() { queueint 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; }