2859 「BalticOI 2009 Day1」地铁信号故障

译自 BalticOI 2009 Day1 T3「Subway Signalling Error」

Stockholm 城中的地铁由几条线路组成。在这个题目中，我们特别考虑其中一条线路，当出现“信号故障”时问题常发生在这里。

一条线路可以看做两条平行的铁轨，他们在端点处连接。在上部的铁轨中，地铁由右到左行驶，且在下部的铁轨中，地铁由左到右行驶。当一列地铁到达铁轨的端点，它会切换到另一条铁轨并更改方向，这个过程在瞬间内完成。

正常情况下，交通流是连续的且地铁匀速移动（$1$ 距离单位每时间单位）。同时，地铁是均匀分布的，即地铁将定时经过铁轨上的每个地点。你可以忽略地铁接客的时间。

由于信号故障，现在地铁沿着线路随机分布。作为交通调度员，你的任务是尽快还原地铁为均匀分布。写一个程序，对于给定的地铁的位置，问何时能还原。你可以使地铁在任意地点暂停或是改变方向（两项可以同时执行）。如果一列地铁改变了方向，他将切换到另一条铁路。

图 1：两条铁轨的长度都是 $100$。上例中，地铁分别位于 $5$（朝右）$,35$（左）$,46$（左）$,75$（左）及 $85$（右）。一个可行的方案是：待位于 $46$ 的地铁向左移动一个单位后，使它改变方向。这用了一个单位的时间。然而，这并不是最优解，详见样例 1。

第一行，两个整数 $m$ 和 $n$，分别表示铁轨的长度和地铁的数量。

以下 $n$ 行，每行表示一列地铁，为一个整数 $x_i$ 表示位置和一个字符表示方向（L 表示左，R 表示右）。

输出使地铁均匀分布的最短时间。最大误差为 $10^{-6}$。