题目 D：电梯调度 (Elevators)

题目描述

在新加坡参加 IOI 2020 期间，所有选手都住在一栋共有 $K$ 层（编号 $1, 2, \dots, K$）的大楼里。大楼安装了 $N$ 部电梯，每部电梯初始都在第 1 层。每部电梯在任何时刻最多只能载 $P$ 人。 电梯速度很快，移动 1 层需要 1 秒，选手开关门、上下电梯的时间忽略不计。

你决定通过编写代码控制电梯系统，以最小化所有选手从到达电梯口到被送达目标层的总等待时间之和。

输入格式

• 第一行：四个整数 $N, P, K, C$，分别表示电梯数、最大载客量、总楼层数和选手总数。
• 接下来 $C$ 行：每行三个整数 $t_i, s_i, e_i$，表示第 $i$ 个选手到达的时间、起始楼层和目标楼层。输入已按 $t_i$ 非递减顺序排列。

输出格式

• 输出应包含 $2C$ 行。每行三个整数 $n_i, c_i, p_i$：
  • $n_i$：执行命令的电梯编号 ($1 \le n_i \le N$)。
  • $c_i$：命令类型（$1$ 为接人，$0$ 为放人）。
  • $p_i$：选手的索引编号（$1 \le p_i \le C$）。

约束条件：

1. 任何时刻电梯内人数 $\le P$。
2. 每个选手必须先被接走（$c=1$）再被放下（$c=0$）。
3. 电梯按输出中该电梯对应的命令顺序执行。如果命令要求去接还没到达的选手，电梯会在该层等待。
4. 电梯之间相互独立，不需要等待其他电梯完成命令。

好的，这是 Problem D: Elevators 的输入与输出数据样例及详细的逻辑解析。

这个样例非常重要，因为它展示了电梯是如何在不同时间点处理多名选手的。

1. 样例输入 (input_*.txt)

2 2 15 5
1 3 5
3 5 4
4 4 10
5 3 10
7 9 1

参数解读：

• $N=2$（2 部电梯）, $P=2$（载客量 2）, $K=15$（15 层楼）, $C=5$（5 名选手）。
• 选手 1：$1s$ 到达，$3$ 层 $\to 5$ 层。
• 选手 2：$3s$ 到达，$5$ 层 $\to 4$ 层。
• 选手 3：$4s$ 到达，$4$ 层 $\to 10$ 层。
• 选手 4：$5s$ 到达，$3$ 层 $\to 10$ 层。
• 选手 5：$7s$ 到达，$9$ 层 $\to 1$ 层。

2. 样例输出 (output_*.txt)

1 1 1
1 1 2
1 0 2
1 0 1
1 1 3
2 1 4
1 0 3
2 0 4
1 1 5
1 0 5