[BOI 2009] Subway Signalling Error

문제: http://www.csc.kth.se/contest/boi/subway.pdf
해법: http://www.csc.kth.se/contest/boi/subway-spoiler.pdf

이 문제에 대한 증명을 하지는 못 하겠다... 그냥 느낌으로 올 뿐이지 증명이 가능한지는... 잘 모르겠다... ㅠㅠ

예제 2번 데이터를 통하여, 방법을 설명하겠다.

1. 우선 처음에 입력 받을 때 방향에 상관없이 입력받고, 오름차순 정렬을 한다.

9 15 33 33 41 81 97 100

2. 홀수번째와 짝수번째의 방향을 다르게 한다.

9R 15L 33R 33L 41R 81L 97R 100L

3. 다음에 subway의 rail을 일직선에 나타내고 그에 따라 x좌표를 대입한뒤 정렬하면,

9 (200-15) 33 (200-33) 41 (200-81) 97 (200-100)

9 33 41 97 100 119 167 185

4. 이제 각 i번째 점에 (2L/N)*(i-1) 만큼의 값을 빼준다.

9 8 -9 22 0 -6 17 10

최대값 M=22, 최소값 m=-9 이다.
답은 (M-m)/2 = 15.5 이다.

총 시간복잡도는 O(N log N) 이다.
증명은 확실히 모르겠고, 4번 같이 한 이유는 (2L/N)*(i-1) 만큼을 빼줌으로써 각 점의 상대적인 위치를 구할 수 있고, 문제에서 구하는건 이동시간 중 최대값의 최소시간이므로 그 상대적인 위치의 (최대값-최소값)/2 이 최소값이 된다.
어찌보면 당연하면서도, 어찌보면 과연 저렇게 하는게 맞을까 싶은 부분은 2번 과정이다...

subway.cpp