레이팅 미적용농부 존(Farmer John)은 방금 아주 많은 건초 더미를 주문했다. 존은 이것들을 원형으로 배열된 N개 (1 <= N <= 100,000)의 무더기로 정리하고 싶어 하며, 무더기 i에는 B_i개의 건초 더미가 있어야 한다. 안타깝게도 건초를 배달한 트럭 기사는 농부 존이 이 정보를 알려줄 때 제대로 듣지 않아서, 건초를 원형으로 배열된 N개의 무더기로 남겨 두라는 것만 기억했다. 배달 후 농부 존이 확인해 보니 무더기 i에는 A_i개의 건초 더미가 있다. 물론 A_i들의 합과 B_i들의 합은 같다.
농부 존은 건초 더미들을 현재 배치(A_i들로 표현)에서 원하는 목표 배치(B_i들로 표현)로 옮기고 싶어 한다. 건초 더미 하나를 원을 따라 x칸 떨어진 무더기로 옮기는 데는 x 단위의 일이 든다. 존이 들여야 하는 일의 최소량을 계산하는 것을 도와주자.
첫째 줄: 정수 N.
둘째 줄부터 1+N번째 줄까지: i+1번째 줄에 두 정수 A_i와 B_i (1 <= A_i, B_i <= 1000)가 주어진다.
건초를 목표 배치로 옮기는 데 필요한 일의 최소량.
restack.in · 출력을 쓸 파일 restack.out4
7 1
3 4
9 2
1 1313Input details: There are 4 piles around a circle. Initially, the piles contain 7, 3, 9, and 1 bales of hay. Farmer John would like to move them so the piles contain 1, 4, 2, and 13 bales of hay.
Output details: A minimum of 13 units of work is required (move 6 bales from pile 1 to pile 4, move 1 bale from pile 3 to pile 2, and move 6 bales from pile 3 to pile 4).