题目描述
停车场有一个塔式结构，高度为 hhh 层，每层有一个长度为 lll 的环形传送带。电梯位于第一层入口（位置 000 ），可以在各层之间垂直移动，到达某一层后会与该层的传送带连接。每层传送带可以顺时针或逆时针旋转，将车辆移动到电梯位置。
取车规则：按车辆编号 1,2,3,…1, 2, 3, \\dots1,2,3,… 的顺序依次取车。每取一辆车的过程如下：
移动时间：
- 电梯每移动一层：101010 秒
- 传送带每移动一个车位：555 秒
输入初始停车布局（ −1-1−1 表示空位，正数表示车辆编号），求取完所有车辆所需的总时间。
题目分析
关键点解析
环形传送带
每层传送带是环形的，长度为 lll ，位置编号从 000 到 l−1l-1l−1 。传送带可以顺时针或逆时针旋转，因此从当前位置 ppp 移动到目标位置 qqq 的最短距离为：
min((q−p+l) mod l, (p−q+l) mod l)
\\min\\big((q – p + l) \\bmod l,\\ (p – q + l) \\bmod l\\big)
min((q−p+l)modl, (p−q+l)modl)
乘以 555 即为旋转时间。
电梯与传送带的连接位置
电梯每次到达某一层时，并不是固定连接该层的 000 号位置。实际上，电梯在该层有一个“当前连接位置”，这个位置会随着取车操作而改变：
当电梯在该层取走位置 xxx 上的车辆后，电梯本身占据了该位置（因为车辆从传送带移到电梯上），所以下一次电梯再来到这一层时，它连接的是上次取车时车辆原来的位置 xxx 。
因此需要为每一层单独维护一个变量 elevatorPos[floor]\\texttt{elevatorPos[floor]}elevatorPos[floor] ，表示电梯下一次到达该层时所连接的位置。
初始状态
- 所有层的 elevatorPos[floor]=0\\texttt{elevatorPos[floor]} = 0elevatorPos[floor]=0 （电梯初始在第一层位置 000 ，其他层虽然没有电梯，但可以理解为该层传送带的 000 位置与电梯井对齐）
- 电梯当前所在楼层 currentFloor=0\\texttt{currentFloor} = 0currentFloor=0 （第 111 层索引为 000 ）
取车流程
对于编号为 carcarcar 的车辆，设其位于 targetFloor\\texttt{targetFloor}targetFloor 层的 targetPos\\texttt{targetPos}targetPos 位置：
- 电梯移动时间： ∣targetFloor−currentFloor∣×10\\lvert \\texttt{targetFloor} – \\texttt{currentFloor} \\rvert \\times 10∣targetFloor−currentFloor∣×10
- 传送带旋转时间：
该层当前连接位置为 elevatorPos[targetFloor]\\texttt{elevatorPos[targetFloor]}elevatorPos[targetFloor] ，将目标车辆旋转到此位置的最短距离为：
min((targetPos−elevatorPos[targetFloor]+l) mod l, (elevatorPos[targetFloor]−targetPos+l) mod l)×5
\\min\\big((\\texttt{targetPos} – \\texttt{elevatorPos[targetFloor]} + l) \\bmod l,\\ (\\texttt{elevatorPos[targetFloor]} – \\texttt{targetPos} + l) \\bmod l\\big) \\times 5
min((targetPos−elevatorPos[targetFloor]+l)modl, (elevatorPos[targetFloor]−targetPos+l)modl)×5 - 更新该层电梯位置：取车后，电梯在该层的位置变为 targetPos\\texttt{targetPos}targetPos
elevatorPos[targetFloor]=targetPos
\\texttt{elevatorPos[targetFloor]} = \\texttt{targetPos}
elevatorPos[targetFloor]=targetPos - 电梯返回第一层：时间 targetFloor×10\\texttt{targetFloor} \\times 10targetFloor×10 （第一层返回时间为 000 ）
- 更新当前楼层： currentFloor=0\\texttt{currentFloor} = 0currentFloor=0
关于最后一辆车
最后一辆车也需要返回第一层，因为客户是在第一层入口取车。题目示例也印证了这一点（若最后一辆车不返回，总时间会减少）。
时间复杂度
每个测试用例需要处理 NNN 辆车（ N≤h×l≤2500N \\le h \\times l \\le 2500N≤h×l≤2500 ），每辆车的处理为 O(1)O(1)O(1) ，因此总时间复杂度 O(h×l)O(h \\times l)O(h×l) ，在给定约束下完全可以接受。
解题步骤
- 读取 hhh 和 lll 。
- 遍历 h×lh \\times lh×l 的停车布局，对每个正数 valvalval ，记录：
- carFloor[val]=i\\texttt{carFloor[val]} = icarFloor[val]=i （车辆所在楼层， iii 从 000 开始）
- carPos[val]=j\\texttt{carPos[val]} = jcarPos[val]=j （车辆在传送带上的位置）
- maxCar=max(maxCar, val)\\texttt{maxCar} = \\max(\\texttt{maxCar},\\ val)maxCar=max(maxCar, val) （最大编号，即车辆总数）
- 初始化：
- elevatorPos\\texttt{elevatorPos}elevatorPos 数组，长度为 hhh ，全部赋值为 000
- currentFloor=0\\texttt{currentFloor} = 0currentFloor=0
- totalTime=0\\texttt{totalTime} = 0totalTime=0
- 从 car=1car = 1car=1 到 maxCar\\texttt{maxCar}maxCar 依次处理：
- 计算电梯移动时间并累加
- 计算传送带旋转时间并累加
- 更新 elevatorPos[targetFloor]\\texttt{elevatorPos[targetFloor]}elevatorPos[targetFloor]
- 累加返回第一层的时间
- 设置 currentFloor=0\\texttt{currentFloor} = 0currentFloor=0
- 输出 totalTime\\texttt{totalTime}totalTime
示例验证
示例输入
2
1 5
-1 2 1 -1 3
3 6
-1 5 6 -1 -1 3
-1 -1 7 -1 2 9
-1 10 4 1 8 -1
示例输出
25
320
解析：
- 第一个测试用例： h=1, l=5h=1,\\ l=5h=1, l=5 ，只有一层。取车顺序 1→2→31 \\to 2 \\to 31→2→3 。电梯无需移动，只需旋转传送带。初始 elevatorPos[0]=0\\texttt{elevatorPos[0]}=0elevatorPos[0]=0 。取车 111 （位置 222 ）：顺时针 222 步 =10=10=10 秒，返回 000 秒，总 101010 秒，更新位置为 222 。取车 222 （位置 111 ）：逆时针 111 步 =5=5=5 秒，总 151515 秒，更新位置为 111 。取车 333 （位置 444 ）：顺时针 333 步 =15=15=15 秒，总 303030 秒？但输出为 252525 —— 检查发现：取车 222 后位置为 111 ，取车 333 在位置 444 ：顺时针距离 (4−1+5)%5=3(4-1+5)\\%5=3(4−1+5)%5=3 ，逆时针距离 (1−4+5)%5=2(1-4+5)\\%5=2(1−4+5)%5=2 ，取最小值 2×5=102 \\times 5 = 102×5=10 秒，所以 10+5+10=2510+5+10=2510+5+10=25 。正确。
完整代码
// Tower Parking
// UVa ID: 12132
// Verdict: Accepted
// Submission Date: 2026-05-28
// UVa Run Time: 0.000s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net
#include <bits/stdc++.h>
using namespace std;
int main() {
int testcases;
scanf("%d", &testcases);
while (testcases—) {
int h, l;
scanf("%d %d", &h, &l);
// 记录每辆车所在的楼层和位置，车辆编号最大为 h*l
vector<int> carFloor(2505, –1);
vector<int> carPos(2505, –1);
int maxCar = 0;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < l; ++j) {
int val;
scanf("%d", &val);
if (val != –1) {
carFloor[val] = i;
carPos[val] = j;
if (val > maxCar) maxCar = val;
}
}
}
// elevatorPos[floor] 表示电梯在该层当前连接的位置
vector<int> elevatorPos(h, 0);
int currentFloor = 0; // 电梯当前所在楼层
int totalTime = 0;
for (int car = 1; car <= maxCar; ++car) {
int targetFloor = carFloor[car];
int targetPos = carPos[car];
// 1. 电梯移动到目标楼层
totalTime += abs(targetFloor – currentFloor) * 10;
// 2. 传送带将目标车旋转到电梯位置
int distClockwise = (targetPos – elevatorPos[targetFloor] + l) % l;
int distCounterClockwise = (elevatorPos[targetFloor] – targetPos + l) % l;
totalTime += min(distClockwise, distCounterClockwise) * 5;
// 3. 更新该层电梯连接位置（车被取走后，电梯占据该位置）
elevatorPos[targetFloor] = targetPos;
// 4. 电梯返回第一层
totalTime += targetFloor * 10;
// 5. 更新当前楼层
currentFloor = 0;
}
printf("%d\\n", totalTime);
}
return 0;
}
注意事项
- 使用 000 索引表示楼层和位置，便于取模运算
- 环形距离计算需要加 lll 再取模，避免负数
- 最后一辆车也需要返回第一层，因为客户在第一层入口取车
- 每层的电梯连接位置必须独立维护，不能假设总是 000
