실행 시간 제한 | 메모리 제한 |
---|---|
1 초 | 128 MB |
노란택시 기사 수철은 도시의 다른 사람들을 위해 택시를 운영하고 있습니다. 사람들은 길이 M(1 <= M <= 1,000,000,000)의 도로를 따라 다른 위치에 모여 있었습니다. 사람들은 택시를 잡으려고 하는데, 잡히지 않자 도로를 따라 다른 곳으로 이동할 에정입니다. 수철은 사람들을 그들의 출발 위치에서 태우고 목적지까지 운전해야 합니다. 수철의 차는 작아서 한 번에 한 명의 사람만 차에 실을 수 있습니다. 사람들은 차에 순식간에 타거나 내릴 수 있습니다.
연료를 아끼기 위해, 수철은 운전해야 할 거리를 최소화하고 싶습니다. N 명의 사람의 출발 위치와 도착 위치 (1 <= N <= 100,000)가 주어졌을 때, 수철이 운전해야 할 최소 거리를 찾아내십시오. 수철은 가스를 많이 아끼기 위해 때때로 사람들을 목적지가 아닌 다른 위치에서 내려줘야 한다는 것을 깨달았습니다.
수철은 도로의 가장 왼쪽 지점, 0 위치에서 시작하여 도로의 가장 오른쪽 지점, M 위치에서 택시 운행을 마무리해야 합니다.
2 10 0 9 6 5
12