파일 업로드

택시 운전

profile
실행 시간 제한메모리 제한
1 초128 MB
📃 해결할 문제

노란택시 기사 수철은 도시의 다른 사람들을 위해 택시를 운영하고 있습니다. 사람들은 길이 M(1 <= M <= 1,000,000,000)의 도로를 따라 다른 위치에 모여 있었습니다. 사람들은 택시를 잡으려고 하는데, 잡히지 않자 도로를 따라 다른 곳으로 이동할 에정입니다. 수철은 사람들을 그들의 출발 위치에서 태우고 목적지까지 운전해야 합니다. 수철의 차는 작아서 한 번에 한 명의 사람만 차에 실을 수 있습니다. 사람들은 차에 순식간에 타거나 내릴 수 있습니다.

연료를 아끼기 위해, 수철은 운전해야 할 거리를 최소화하고 싶습니다. N 명의 사람의 출발 위치와 도착 위치 (1 <= N <= 100,000)가 주어졌을 때, 수철이 운전해야 할 최소 거리를 찾아내십시오. 수철은 가스를 많이 아끼기 위해 때때로 사람들을 목적지가 아닌 다른 위치에서 내려줘야 한다는 것을 깨달았습니다.

수철은 도로의 가장 왼쪽 지점, 0 위치에서 시작하여 도로의 가장 오른쪽 지점, M 위치에서 택시 운행을 마무리해야 합니다.

💻 입력
  • 첫 번째 줄 : 공백으로 구분된 N과 M.
  • 두 번째 줄부터 1+N 번째 줄 : (i + 1)번째 줄에는 두 개의 공백으로 구분된 정수 s_i 와 t_i (0 <= s_i, t_i <= M)가 포함되어 있고, 이는 i번째 사람의 출발 위치와 도착 위치를 나타냅니다.
🖨️ 출력
  • 첫 번째 줄 : 수철이 운전해야 하는 총 거리를 나타내는 단일 정수. 결과는 32비트 정수에 맞지 않을 수 있습니다.

💻 예제 입력 1
2 10
0 9
6 5
🖨️ 예제 출력 1
12

출처: USACO 2013 February Contest, Gold Problem 2. Taxi