Train Scheduling

题目描述

注意：本题的内存限制为 512MB，是默认值的两倍。 Bessie 找到了一份新工作，担任列车调度员！有两个火车站：$A$ 和 $B$。由于预算限制，连接两站的铁轨只有一条单线。若一列火车在时间 $t$ 从某站出发，则会在时间 $t+T$ 到达另一站（$1\le T\le 10^{12}$）。 有 $N$（$1\le N\le 5000$）列火车需要安排出发时间。第 $i$ 列火车必须在时间 $t_i$ 或更晚从车站 $s_i$ 出发（$s_i\in \{A, B\}, 0\le t_i\le 10^{12}$）。不允许在同一时间有火车沿着铁轨相向行驶（否则会相撞）。不过，允许同一时间有多列火车沿相同方向在轨道上行驶（假设火车长度可忽略不计）。 请帮助 Bessie 安排所有火车的出发时间，使得不会发生相撞，并使总延误最小。若第 $i$ 列火车被安排在时间 $a_i\ge t_i$ 出发，则总延误定义为 $\sum_{i=1}^N(a_i-t_i)$。

输入格式

第一行包含 $N$ 和 $T$。 接下来 $N$ 行，其中第 $i$ 行包含车站 $s_i$ 和时间 $t_i$，对应第 $i$ 列火车。

输出格式

输出在所有合法调度方案中可能达到的最小总延误。

1 95
B 63

0

4 1
B 3
B 2
A 1
A 3

1

4 10
A 1
B 2
A 3
A 21

13

8 125000000000
B 17108575619
B 57117098303
A 42515717584
B 26473500855
A 108514697534
B 110763448122
B 117731666682
A 29117227954

548047356974

提示

唯一的一列火车准时出发。 有两种最优调度方案。一种做法是让火车 $2,3,4$ 准时出发，让火车 $1$ 延迟一分钟出发。另一种是让火车 $1,2,3$ 准时出发，让火车 $4$ 延迟一分钟出发。 最优调度是让火车 $1$ 和 $3$ 准时出发，让火车 $2$ 在时间 $13$ 出发，让火车 $4$ 在时间 $23$ 出发。总延误为 $0+11+0+2=13$。 评分： 测试点 5-6：$N \le 15$ 测试点 7-10：$N \le 100$ 测试点 11-14：$N \le 500$ 测试点 15-18：$N\le 2000$ 测试点 19-24：无额外限制 题目作者：Brandon Wang

标签: USACO|2023|Platinum

来源

USACO|2023|Platinum