问题分析

我们有一个电梯系统，规则比较复杂：

初始电梯在 $1$ 楼（地面层）。

雇员 $i$ 在 $t_i$ 时刻到达 $a_i$ 层电梯口。

如果该层已有人按过电梯，则他等待；否则他按电梯，产生一个请求信号。

电梯空闲时，会响应最早的请求（时间 $t_i$ 最小，同时间则编号 $i$ 最小）。

电梯每秒移动 $1$ 层（上升或下降）。

电梯上升时，只接目标楼层的人；下降时，会顺路接所有经过的有请求的楼层的人。

忽略进出电梯时间。

问每个雇员到达 $1$ 楼的时间。

---

关键观察

请求信号：每个楼层第一次有人到达的时间，就是该楼层的请求时间。 设楼层 $f$ 的第一个到达者的到达时间为 $req_f$，若该楼层无人，则 $req_f = \infty$。

电梯运行模式：

从 $1$ 楼出发到某个目标楼层 $target$（上升），耗时 $target - 1$ 秒。

在该楼层接人（瞬间完成）。

然后下降，途中经过有请求且未处理的楼层就停，直到 $1$ 楼。

下降耗时也是 $target - 1$ 秒吗？不，因为可能中间停靠，但下降总距离仍是 $target - 1$ 层，每层 $1$ 秒，停靠不额外耗时（题目说忽略进出时间），所以下降时间 = 从 $target$ 到 $1$ 的层数差 = $target - 1$ 秒。

所以一次完整的“上升-下降”行程总耗时 = $2 \times (target - 1)$ 秒。

下降途中接人：下降时，如果某层有请求且请求时间 ≤ 电梯到达该层的时间，则该层的人会被接走。

空闲时选择下一个目标：选择未处理请求中 $req_f$ 最小的楼层，若多个选楼层编号最小的。

形式化建模:

设 $F$ 为有请求的楼层集合，每个元素是 $(req_f, f)$。

电梯工作循环：

当前时间 $T$，从 $F$ 中选 $req_f \le T$ 且 $req_f$ 最小的，若多个选 $f$ 最小的，作为 $target$。

如果 $F$ 中没有 $req_f \le T$ 的，则 $T$ 推进到 $\min_{f \in F} req_f$，再选。

上升：从 $1$ 楼到 $target$ 层，到达时间 $T + (target - 1)$。

下降：从 $target$ 层到 $1$ 楼，下降过程中，对于 $k = target, target-1, \dots, 2$，如果 $k \in F$ 且 $req_k \le T + (target - 1) + (target - k)$（即请求时间 ≤ 电梯到达该层的时间），则接走该层所有人，并标记该层已处理（从 $F$ 移除）。

到达 $1$ 楼时间 = $T + 2 \times (target - 1)$，这个时间就是该批次所有人到达 $1$ 楼的时间。

更新当前时间 $T$ 为到达 $1$ 楼的时间，重复直到 $F$ 为空。

---

算法设计

数据结构

用优先队列（最小堆）存储 $(req_f, f)$，便于快速找到最早请求。

用哈希表或数组记录每个楼层第一个请求时间 $firstReq[f]$ 和该楼层所有雇员的列表 $people[f]$。

步骤

读入数据，按 $t_i$ 排序（题目已保证 $t_1 \le t_2 \le \dots$）。

计算每个楼层的最早请求时间 $firstReq[f]$，并收集该楼层所有雇员。

将 $(firstReq[f], f)$ 放入优先队列 $pq$。

当前时间 $curTime = 0$。

当 $pq$ 不空：

若 $pq$ 堆顶的 $req > curTime$，则 $curTime = req$（电梯等待）。

弹出 $req \le curTime$ 中 $f$ 最小的请求（因为可能有多个同时 $req$，要选最小楼层）。

实际上，我们每次弹出堆顶，如果它的 $req > curTime$，则放回，并更新 $curTime$ 到堆顶的 $req$，再重新开始这一轮。

但更简单：用一个列表收集所有 $req \le curTime$ 的，选 $f$ 最小的作为 $target$，其余放回。

上升：$arriveTarget = curTime + (target - 1)$。

下降：从 $target$ 到 $1$，对于经过的每个楼层 $k$，如果 $firstReq[k] \le arriveTarget + (target - k)$，则接走该层所有人，并标记该层已处理（从 $pq$ 中删除该楼层请求，如果还在里面）。

这批人到达 $1$ 楼时间 = $curTime + 2 \times (target - 1)$，记录到答案。

更新 $curTime$ 为该时间，重复。

时间复杂度

每个楼层最多入队出队一次。

寻找经过的楼层时，可以预先按楼层排序请求，用指针扫描。

总复杂度 $O(n \log n)$。

---

公式总结

设：

$curTime$：电梯当前时间

$target$：当前目标楼层

$arriveTarget = curTime + (target - 1)$：到达目标楼层的时间

$finishTime = curTime + 2 \times (target - 1)$：回到 $1$ 楼的时间

对于下降过程中楼层 $k$（$target \ge k \ge 2$），电梯到达 $k$ 层的时间为：

$$t_{arriveK}=arriveTarget+(target-k)$$

若 $firstReq[k] \le t_{arriveK}$，则接走该层所有人，他们的答案 = $finishTime$。

---

实现细节

用 heapq 维护 $(firstReq[f], f)$。

用字典 $floor_{people[f]} = list of (t_i, id)$，按 $t_i$ 排序。

用集合 $active_{floors}$记录还有请求的楼层。

每次选目标楼层时，弹出堆顶直到找到 $req \le curTime$ 的最小楼层，其余放回。

下降时从高到低遍历楼层，判断是否接人。