레이팅 미적용농부 존의 \(N\)마리 소들은 늘 농장의 외딴 구석으로 돌아다니곤 한다! 존이 소들을 다시 한데 모으는 것을 도와주자.
농장의 주 목초지는 길고 좁다. 이를 수직선으로 생각할 수 있으며, 소는 임의의 정수 위치를 차지할 수 있다. \(N\)마리 소는 현재 서로 다른 정수 위치에 있으며, 농부 존은 소들이 연속한 위치들(예: 위치 3, 4, 5, 6, 7, 8)을 차지하도록 이동시키고 싶다.
안타깝게도 소들은 꽤 졸린 상태라서, 농부 존은 소들의 주의를 끌어 움직이게 하는 데 애를 먹는다. 어느 시점에서든 존은 "끝점"에 있는 소(모든 소 중 최소 또는 최대 위치에 있는 소)만 움직이게 할 수 있다. 소를 움직일 때, 새 위치에서 더 이상 끝점이 아니게 되는 한, 비어 있는 임의의 정수 위치로 이동하도록 지시할 수 있다. 이러한 종류의 이동을 반복하면 소들이 점점 서로 가까워지는 경향이 있음을 관찰할 수 있다.
소들이 연속한 \(N\)개 위치에 모이기까지 가능한 이동 횟수의 최솟값과 최댓값을 구하시오.
문제 제공: Matthew Fahrbach
문제 제공: Matthew Fahrbach
첫째 줄에 \(N\) (\(3 \leq N \leq 10^5\))이 주어진다. 다음 \(N\)개의 줄 각각에는 소 한 마리의 정수 위치가 주어지며, 범위는 \(1 \ldots 10^9\)이다.
출력의 첫째 줄에는 농부 존이 소들을 한데 모으는 데 필요한 최소 이동 횟수를 출력한다. 둘째 줄에는 소들이 한데 모이기 전까지 존이 할 수 있는 최대 이동 횟수를 출력한다.
herding.in · 출력을 쓸 파일 herding.out3
7
4
91
2The minimum number of moves is 1 --- if Farmer John moves the cow in position 4
to position 8, then the cows are at consecutive locations 7, 8, 9. The maximum
number of moves is 2. For example, the cow at position 9 could be moved to
position 6, then the cow at position 7 could be moved to position 5.
riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > February > Silver