One solution is to binary search for the answer. To test if it's possible to get the trains in order within time ~t~, assume that at least one train has to move exactly the distance ~t~ (since a train can move both left and right, there are ~2n~ possibilities to try). We can now determine where all other ~n-1~ trains must be. To check if this is possible, note that this is a bipartite matching problem where one partition consists of the train's original position, and the other partition consists of a train's final position. An edge exists between nodes in the left and right partition if the distance between the positions are at most ~t~.

Solving the max match problem with standard bipartite matching is too slow however. This can instead be accomplished much more easily by realizing that a greedy approach will work. The train with the leftmost original position can always be assigned to the leftmost of the new positions, and so on. If such an assignment is impossible (because the distance is greater than ~t~), then no max matching exists.

The solution then involves a binary search (about ~30~ iterations or so needed to get the desired precision), fixing the position of one train (~\mathcal O(n)~), and a greedy matching (~\mathcal O(n)~). The overall complexity is thus ~\mathcal O(n^2)~ with a fairly large constant factor due to the binary search.

The optimal solution is more mathematical, and runs in ~\mathcal O(n \log n)~ time: First we notice that if we sort trains from left to right on the line, then the odd trains should be going in one direction and even ones in the other. That is because we are not swapping two trains in an optimal solution, and when the trains are evenly distributed, the odd ones face one direction and the even ones the other. So now we know the directions and we can only move each train to the left or right. Consider the example from the problem statement. After sorting we calculate directions:

$$\displaystyle 9\mathtt R, 15\mathtt L, 33\mathtt R, 33\mathtt L, 41\mathtt R, 81\mathtt L, 97\mathtt R, 100\mathtt L$$

Now it is like we were on the circle of length ~200~:

$$\displaystyle 9, 33, 41, 97, 100, 119, 167, 185$$

Assume that we don't move the first train. In such a situation, we easily calculate where the trains should be:

$$\displaystyle 9, 34, 59, 84, 109, 134, 159, 184$$

and the movements of the trains should be, respectively:

$$\displaystyle 0, -1, -18, 13, -9, -15, 8, 1$$

Now, if the first train moves by ~x~, all the others move by ~a+x~, where ~a~ is the move if first train stands still. If we find minimum and maximum over the moves (~m = -18~ and ~M = 13~), when first train stands, then when it moves by ~x~, the minimum and maximum will be ~m+x~ and ~M+x~. Our result would then be ~\max(|m+x|, |M+x|)~. This is minimized when ~m+x = -(M+x)~, which gives ~x = \frac{-M-m}{2}~ and thus the final result is ~M+x = \frac{M-m}{2}~, i.e., ~15.5~ in the example. The whole algorithm runs in ~\mathcal O(N \log N)~.