레이팅 미적용농부 존(Farmer John)은 자신의 소 몇 마리를 촬영하기 위해 전문 사진작가를 고용했다. FJ의 소들은 다양한 품종으로 이루어져 있으므로, 존은 사진에 무리에 존재하는 서로 다른 품종마다 적어도 한 마리씩 담기기를 원한다.
FJ의 N마리 소는 모두 일직선 위의 여러 위치에 서 있으며, 각 소는 정수 위치(즉, x 좌표)와 정수 품종 ID로 설명된다. FJ는 직선 위에서 연속한 범위의 소들을 사진에 담을 계획이다. 사진의 비용은 그 크기와 같다. 즉, 사진 범위에 포함된 소들의 x 좌표 최댓값과 최솟값의 차이이다.
FJ의 무리에 나타나는 서로 다른 품종마다 적어도 한 마리가 담기는 사진의 최소 비용을 계산하여 FJ를 도와주자.
첫째 줄: 소의 수 N (1 <= N <= 50,000).
둘째 줄부터 1+N번째 줄까지: 각 줄에 소 한 마리의 x 좌표와 품종 ID를 나타내는, 공백으로 구분된 두 양의 정수가 주어진다. 두 수 모두 최대 10억이다.
서로 다른 모든 품종 ID를 담는 사진의 최소 비용.
lineup.in · 출력을 쓸 파일 lineup.out6
25 7
26 1
15 1
22 3
20 1
30 14Input details: There are 6 cows, at positions 25,26,15,22,20,30, with respective breed IDs 7,1,1,3,1,1.
Output details: The range from x=22 up through x=26 (of total size 4) contains each of the distinct breed IDs 1, 3, and 7 represented in FJ's herd.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > November > Silver