레이팅 미적용농부 존이 가장 싫어하는 농장 일 중 하나는 소똥을 잔뜩 실어 나르는 것이다. 이 과정을 간소화하기 위해 그는 기발한 발명품을 생각해 냈다. 바로 소똥 순간이동 장치이다! 트랙터 뒤에 수레를 달고 두 지점 사이에서 소똥을 실어 나르는 대신, 소똥 순간이동 장치를 사용하면 소똥을 한 위치에서 다른 위치로 즉시 옮길 수 있다.
농부 존의 농장은 하나의 길고 곧은 도로를 따라 지어져 있어서, 농장의 어떤 위치든 이 도로 상의 위치(사실상 수직선 위의 한 점)만으로 간단히 나타낼 수 있다. 순간이동 장치는 두 수 \(x\)와 \(y\)로 표현되며, 위치 \(x\)로 가져온 소똥을 위치 \(y\)로 즉시 옮길 수 있다.
농부 존은 첫 번째 끝점이 \(x=0\)에 위치한 순간이동 장치를 만들기로 했다. 여러분의 임무는 다른 끝점 \(y\)의 최적 위치를 정하도록 돕는 것이다. 구체적으로, 농장에는 \(N\)개의 소똥 더미가 있다 (\(1 \leq N \leq 100,000\)). \(i\)번째 더미는 위치 \(a_i\)에서 위치 \(b_i\)로 옮겨야 하며, 농부 존은 각 더미를 다른 더미들과 별도로 운반한다. \(i\)번째 더미를 나를 때 농부 존이 소똥을 트랙터에 싣고 운전하는 거리를 \(d_i\)라 하면, \(i\)번째 더미를 트랙터로 직접 나른다면 \(d_i = |a_i-b_i|\)일 수 있고, 순간이동 장치를 사용한다면(예를 들어 트랙터로 \(a_i\)에서 \(x\)까지 나른 다음 \(y\)에서 \(b_i\)까지 나르는 식으로) \(d_i\)가 더 작아질 수도 있다.
순간이동 장치의 다른 끝점 \(y\)를 신중하게 선택한 최적의 위치에 만들어서 농부 존이 달성할 수 있는 \(d_i\)들의 합의 최솟값을 구하도록 도와주자. 모든 더미의 운반에 같은 위치 \(y\)가 사용된다.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(N\)이 주어진다. 이어지는 \(N\)개의 줄 중 \(i\)번째 줄에는 각각 \(-10^8 \ldots 10^8\) 범위의 정수인 \(a_i\)와 \(b_i\)가 주어진다. 이 값들이 모두 서로 다르지는 않을 수 있다.
농부 존이 달성할 수 있는 \(d_i\)들의 합의 최솟값을 나타내는 수 하나를 출력한다. 이 수는 표준 32비트 정수에 담기에 너무 클 수 있으므로, C/C++의 "long long" 같은 큰 정수 자료형을 사용해야 할 수도 있다. 또한 답이 반드시 정수인지 아닌지도 생각해 보는 것이 좋다...
teleport.in · 출력을 쓸 파일 teleport.out3
-5 -7
-3 10
-2 710In this example, by setting \(y = 8\) FJ can achieve \(d_1 = 2\), \(d_2 = 5\), and
\(d_3 = 3\). Note that any value of \(y\) in the range \([7,10]\) would also yield an
optimal solution.
riseoj 작성
출처 올림피아드 > USACO > 2017-2018 > February > Silver