프로그램 명: coci_cestarine
제한시간: 1 초
[문제요약]
어느날 루카는 고속도로를 여행하고 있다. 이 고속도로는 많은 진입로와 진출로가 있다.
특별한 숫자를 가진 진출로는 그 번호를 가진 진입로와 같은 위치에 있다.
고속도로에 진입하면 트럭 운전사는 그가 사용한 진입로를 가르키는 티켓을 받는다.
그리고 고속도로를 벗어날 때 운전사는 진입로와 진출로의 번호의 차이만큼의 톨비를 지불해야 한다.
예를 들어, 30 번 진입로를 12 번 진출로로 나갔다면 18 의 톨비를 지불한다.
그는 그의 회사가 매일 지출하는 톨비를 절약하는 방법을 알아내었다.
두 운전사가 고속도로에서 만나서 티켓을 교환한다면. (단, 길이 중복되지 않는다 할지라도 교환 가능)
티켓은 원하는 횟수만큼 교환할 수 있지만 의심 받을수 있기 때문에 같은 진입로와 진출로를 이용할 수는 없다.
티켓을 교환해서 최소의 톨비를 구하는 프로그램을 작성하는 것이 문제이다.
In a single day, N of Luka's trucks travel a specific highway. The highway has a number of exits and entrances. An exit with a particular number is in the same location as the entrance with that number.
Upon entering the highway, a truck driver receives a ticket which indicates the entrance he used. When
exiting, the driver pays a toll equal to the absolute difference of the entrance and exit numbers.
For example, if a ticket says he used entrance 30, then exiting at exit 12 will cost him 18.
Luka has figured out a way to save toll money that his company daily spends. Any two drivers can meet on the highway and exchange tickets, even if their routes don't overlap. Tickets can be exchanged an
arbitrary number of times.
However, a driver cannot use an exit if his ticket says he used the same entrance, since that
would be suspicious.
Write a program that calculates the least total amount of tolls that the drivers can achieve by
exchanging tickets.
입력
The first line contains the integer N (1 ≤ N ≤ 100000), the number of trucks.
Each of the following N lines contains two distinct integers between 1 and 1000000. These are in order
the entrance and exit numbers of one truck.
No two trucks will use the same highway entrance or the same exit.
출력
Output the least total amount of tolls Luka's company must pay.
Note: use 64-bit integer types (long long in C/C++, int64 in Pascal).
입출력 예
input
3
3 65
45 10
60 25
output
32
input
3
5 5
6 7
8 8
output
5
Sample test data
In the first example, the first and third drivers will exchange tickets. After this, the second and third
drivers exchange tickets. After this, the drivers will have the tickets 60, 3, 45, respectively. The total
amount in tolls is |65-60| + |10-3| + |25-45| = 32.
출처:coci 2007-2008 contest6 6/6
[질/답]
[제출 현황]
[푼 후(0)]