G. 电动滑板车 详细题解

题目核心理解

校园里有 $n$ 栋楼，每栋楼有课程类型 $c_i$（C/M/-），并可能有一位对应学科的教授 $p_i$。 你驾驶一辆最多载一名教授的滑板车，每栋楼最多前往一次，可以在楼上接教授（PICKUP）或放教授（DROPOFF）。

要求最终满足：

• 所有有 C 课的楼必须有 C 教授
• 所有有 M 课的楼必须有 M 教授

你需要构造一组合法操作序列，题目保证一定有解。

---

核心思路

1. 关键性质

• 满足 $c_i=p_i$ 的楼已经合法，可以直接忽略，不需要任何操作。
• 如果所有楼都满足 $c_i=p_i$，直接输出 $0$ 步即可。
• 不合法的教授，一定是从不需要该教授的楼运到需要该教授的楼。
• 无课楼（$c_i=-$）可以作为中转点，保证运送过程合法。

2. 贪心规则

• 优先处理多余教授：把有课楼里不需要的教授移到无课楼。
• 再把缺少教授的楼用对应类型教授补齐。
• 全程保证：每栋楼只去一次，车上最多一名教授。

3. 简化策略

只需要按固定顺序处理：

1. 找到一个有某类教授、但不需要该教授的楼
2. 开车过去接走教授
3. 开到需要该教授的楼放下
4. 重复直到所有课程匹配完成

---

算法流程

1. 遍历所有楼，跳过已经合法（$c_i=p_i$）的楼。
2. 对于每一位不合法的教授：
   • 找到其所在楼 $u$
   • 记录 DRIVE u + PICKUP
   • 找到需要该教授的目标楼 $v$
   • 记录 DRIVE v + DROPOFF
3. 所有楼只访问一次，不重复驾驶。
4. 按顺序输出所有操作。

---

公式与复杂度分析

合法条件：

$$\forall i,\ c_i \neq \text{`-'} \implies p_i = c_i $$

复杂度

• 遍历与构造路线：$O(n)$
• 总时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

可轻松处理 $n \le 2000$ 的数据范围，在 $2$ 秒时限内稳定通过。