地铁信号错误 - 문제

斯德哥尔摩的地铁由数条地铁线路组成。在本题中，我们将特别考虑其中一条线路，以及当发生“信号错误”时该线路上经常出现的问题。

一条地铁线路可以看作是两条在端点处相连的平行轨道。在上层轨道上，列车从右向左行驶；在下层轨道上，列车从左向右行驶。当列车到达轨道的端点时，它会切换到相反的轨道并改变方向。这种切换是瞬间完成的，不消耗时间。

在正常交通情况下，交通流是连续的，列车以恒定的速度（每单位时间 1 个长度单位）移动。列车是均匀分布的；也就是说，在轨道的任何给定位置，列车都会周期性地出现。我们假设列车停车和接载乘客所花费的时间可以忽略不计。

现在，由于信号错误，列车在沿线随机分布。作为交通管理器，你的任务是尽快确保列车再次沿线均匀分布。编写一个程序，在给定当前列车位置的情况下，计算实现这一目标的最快时间。你被允许命令列车在沿线的任何地方暂时停止和/或改变方向。如果列车改变方向，它将从一条轨道移动到另一条轨道。

图 1：两条轨道的长度均为 100。在上方示例中，列车分别位于 5（向右）、35（向左）、46（向左）、75（向左）和 85（向右）。使列车均匀分布的一种方法是让位于位置 46 的列车向左行驶一个单位，然后改变方向。这需要一个单位的时间。然而，这并不是最优解；参见下方的样例 1。

输入从标准输入读取。

输入的第一行包含两个由单个空格分隔的整数：地铁轨道的长度 $m$ 和线路上的列车数量 $n$。

接下来的 $n$ 行，每行描述一辆列车的当前位置。每行包含一个整数 $x_i$ 和一个方向（L 表示向左，R 表示向右），两者之间由单个空格分隔。

你的程序应该向标准输出输出单行，包含使列车均匀分布所需的最短时间。你的程序输出的绝对误差应不超过 $10^{-6}$。

0.5

15.500000

对于占总分 50% 的测试用例，$n \le 200$。

QOJ.ac