A6152. 「USACO 2023.12 Platinum」Train Scheduling
编程题
省选/NOI-
知识点
题目描述
**题目译自 [USACO 2023 December Contest, Platinum](http://usaco.org/index.php?page=dec23results) Problem 3. [Train Scheduling](http://usaco.org/index.php?page=viewproblem2&cpid=1358)**
Bessie 有了一份新工作：火车调度员！有两个火车站 $A$ 和 $B$。由于预算限制，这两个车站之间只有一条轨道。如果火车在时刻 $t$ 离开火车站，那么它会在时刻 $t+T$ 到达另一个火车站。
有 $N$ 趟火车的出发时间需要被安排。第 $i$ 趟火车必须在时刻 $t_i$ 或之后离开 $s_i$ 站。不允许火车同时在轨道上相向而行（因为它们会相撞）。然而，允许轨道上有许多火车同时向同一方向行驶（假设列车的大小可以忽略不计）。
请帮 Bessie 安排所有火车的出发时间，满足火车不会相撞，并且总晚点时间最小。如果火车 $i$ 计划在时刻 $a_i\ge t_i$ 出发，则总晚点时间定义为 $\sum_{i=1}^N (a_i-t_i)$。
Bessie 有了一份新工作：火车调度员！有两个火车站 $A$ 和 $B$。由于预算限制，这两个车站之间只有一条轨道。如果火车在时刻 $t$ 离开火车站，那么它会在时刻 $t+T$ 到达另一个火车站。
有 $N$ 趟火车的出发时间需要被安排。第 $i$ 趟火车必须在时刻 $t_i$ 或之后离开 $s_i$ 站。不允许火车同时在轨道上相向而行（因为它们会相撞）。然而，允许轨道上有许多火车同时向同一方向行驶（假设列车的大小可以忽略不计）。
请帮 Bessie 安排所有火车的出发时间，满足火车不会相撞，并且总晚点时间最小。如果火车 $i$ 计划在时刻 $a_i\ge t_i$ 出发，则总晚点时间定义为 $\sum_{i=1}^N (a_i-t_i)$。
输入格式
第一行包含两个整数 $N\ (1\le N\le 5000)$ 和 $T\ (1\le T\le 10^{12})$。
接下来 $N$ 行，第 $i$ 行表示第 $i$ 趟火车的始发站 $s_i\ (s_i\in\{\texttt{A},\texttt{B}\})$ 和预计出发时刻 $t_i\ (0\le t_i\le 10^{12})$。
接下来 $N$ 行，第 $i$ 行表示第 $i$ 趟火车的始发站 $s_i\ (s_i\in\{\texttt{A},\texttt{B}\})$ 和预计出发时刻 $t_i\ (0\le t_i\le 10^{12})$。
输出格式
输出一行，表示对于所有合法调度方案，最小的总晚点时间。
输入输出样例
输入 #1
1 95 B 63
输出 #1
0
输入 #2
4 1 B 3 B 2 A 1 A 3
输出 #2
1
输入 #3
4 10 A 1 B 2 A 3 A 21
输出 #3
13
输入 #4
8 125000000000 B 17108575619 B 57117098303 A 42515717584 B 26473500855 A 108514697534 B 110763448122 B 117731666682 A 29117227954
输出 #4
548047356974
说明/提示
- 测试点 $5\sim 6$：$N\le 15$
- 测试点 $7\sim 10$：$N\le 100$
- 测试点 $11\sim 14$：$N\le 500$
- 测试点 $15\sim 18$：$N\le 2000$
- 测试点 $19\sim 24$：无附加限制
Problem credits: Brandon Wang
- 测试点 $7\sim 10$：$N\le 100$
- 测试点 $11\sim 14$：$N\le 500$
- 测试点 $15\sim 18$：$N\le 2000$
- 测试点 $19\sim 24$：无附加限制
Problem credits: Brandon Wang