RESTACK - Restacking haybales 2012
题意翻译
**【题目来源】**
Usaco-2012-Mar
**【题目描述】**
FJ买了一些干草堆,他想把这些干草堆分成N堆(1<=N<=100,000)摆成一圈,其中第i堆有B_i数量的干草。不幸的是,负责运货的司机由于没有听清FJ的要求,只记住分成N堆摆成一圈这个要求,而每一堆的数量却是A_i(1<=i<=N)。当然A_i的总和肯定等于B_i的总和。
FJ可以通过移动干草来达到要求,即使得A_i=B_i,已知把一个干草移动x步需要消耗x数量的体力,相邻两个干草堆之间的步数为1。
请帮助FJ计算最少需要消耗多少体力才能完成任务。
**【输入】**
第一行输入一个整数N。
接下来N行,每行两个整数,其中第i+1行描述A_i和B_i(1<=A_i,B_i<=1000)。
**【输出】**
输出一个数表示最少需要消耗的体力。
**【样例说明】**
从第1堆中移动6个干草到第4堆,从第3堆中移动1个干草到第2堆,从第3堆中移动6个干草到第4堆中。
题目描述
Farmer John has just ordered a large number of bales of hay. He would like
to organize these into N piles (1 <= N <= 100,000) arranged in a circle,
where pile i contains B\_i bales of hay. Unfortunately, the truck driver
delivering the hay was not listening carefully when Farmer John provided
this information, and only remembered to leave the hay in N piles arranged
in a circle. After delivery, Farmer John notes that pile i contains A\_i
bales of hay. Of course, the A\_i's and the B\_i's have the same sum.
Farmer John would like to move the bales of hay from their current
configuration (described by the A\_i's) into his desired target
configuration (described by the B\_i's). It takes him x units of work to
move one hay bale from one pile to a pile that is x steps away around the
circle. Please help him compute the minimum amount of work he will need to
spend.
输入输出格式
输入格式
\* Line 1: The single integer N.
\* Lines 2..1+N: Line i+1 contains the two integers A\_i and B\_i (1 <=
A\_i, B\_i <= 1000).
Example:
4
7 1
3 4
9 2
1 13