건초 더미 재배치

면접 대비

시간 제한1초메모리 제한128 MB

요약

원형으로 놓인 N개의 더미에서 현재 양과 목표 양이 주어질 때, 원형 거리에 비례하는 비용으로 건초를 옮겨 목표 상태를 만드는 최소 비용을 구한다.

난이도: 보통10점 중 7점
유형: 그리디, 누적 합, 수학, 배열
정답자: 아직 제출이 없습니다

문제

농부 John이 많은 건초 더미를 주문했다. 그는 이 건초를 원형으로 배치된 $N$ 개의 더미( $1 \le N \le 100{,}000$ )로 정리하려고 하며, $i$ 번 더미에는 $B_i$ 개의 건초가 있어야 한다. 그런데 배달 기사는 건초를 원형으로 배치된 $N$ 개의 더미로 내려놓아야 한다는 것만 기억했다. 배달이 끝난 뒤 $i$ 번 더미에는 $A_i$ 개의 건초가 있다. 물론 $A_i$ 의 총합과 $B_i$ 의 총합은 서로 같다.

John은 현재 배치( $A_i$ )를 원하는 목표 배치( $B_i$ )로 바꾸려고 한다. 건초 한 개를 원을 따라 $x$ 칸 떨어진 더미로 옮기는 데는 $x$ 만큼의 작업량이 든다. 필요한 최소 작업량을 구하여라.

입력

첫째 줄: 정수 $N$ .
둘째 줄부터 $N+1$ 번째 줄까지: $i+1$ 번째 줄에 두 정수 $A_i$ 와 $B_i$ 가 주어진다 ( $1 \le A_i, B_i \le 1000$ ).

출력

John이 필요로 하는 최소 작업량을 정수 하나로 출력한다.

힌트

첫 번째 예시에서는 원형으로 배치된 4개의 더미가 처음에 각각 7, 3, 9, 1개의 건초를 가지고 있고, 목표는 1, 4, 2, 13개이다. 최소 13의 작업량이면 충분하다: 1번 더미에서 4번 더미로 6개, 3번 더미에서 2번 더미로 1개, 3번 더미에서 4번 더미로 6개를 옮긴다. 더미가 원을 이루므로 1번 더미와 4번 더미는 서로 인접하며, 따라서 이 이동들은 건초 한 개당 1칸씩만 든다.

예제6

예제 1
입력
```
4
7 1
3 4
9 2
1 13
```
예상 출력
```
13
```
예제 2
입력
```
1
5 5
```
예상 출력
```
0
```
예제 3
입력
```
2
3 3
4 4
```
예상 출력
```
0
```
예제 4
입력
```
2
5 1
1 5
```
예상 출력
```
4
```
예제 5
입력
```
3
10 1
1 1
1 10
```
예상 출력
```
9
```
예제 6
입력
```
5
4 2
2 5
6 1
1 4
2 3
```
예상 출력
```
7
```