레이팅 미적용베시(Bessie)는 농장의 다른 소들을 위해 택시 서비스를 운영하고 있다. 소들은 길이 M (1 <= M <= 1,000,000,000)의 울타리를 따라 여러 위치에 모여 있다. 안타깝게도 소들은 현재 위치가 지겨워져서, 각자 울타리를 따라 다른 곳으로 가고 싶어 한다. 베시는 친구들 각각을 출발 위치에서 태워 목적지까지 데려다주어야 한다. 베시의 차는 작아서 한 번에 소 한 마리만 태울 수 있다. 소들은 차에 순간적으로 타고 내릴 수 있다.
기름을 아끼기 위해, 베시는 운전해야 하는 거리를 최소화하고 싶어 한다. N마리 (1 <= N <= 100,000)의 소 각각의 출발 위치와 도착 위치가 주어질 때, 베시가 해야 하는 최소 운전 거리를 구하시오. 베시는 기름을 최대한 아끼려면 때때로 소를 목적지가 아닌 위치에 내려 줘야 할 수도 있다는 것을 알고 있다.
베시는 울타리의 가장 왼쪽 지점인 위치 0에서 출발하고, 여정을 울타리의 가장 오른쪽 지점인 위치 M에서 마쳐야 한다.
첫째 줄: 공백으로 구분된 N과 M.
둘째 줄부터 1+N번째 줄까지: (i+1)번째 줄에 i번째 소의 출발 위치와 도착 위치를 나타내는, 공백으로 구분된 두 정수 s_i와 t_i (0 <= s_i, t_i <= M)가 주어진다.
베시가 해야 하는 총 운전 거리를 나타내는 정수 하나. 결과가 32비트 정수에 담기지 않을 수 있음에 유의하라.
taxi.in · 출력을 쓸 파일 taxi.out2 10
0 9
6 512Output details: Bessie picks up cow 1 at 0 and drives to 6, drops cow 1, delivers cow 2 to her destination, returns to pick up cow 1, drops her off, then drives to the right end of the fence.
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > February > Gold