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.
给出n块土地，现有泥土A[i]，需要改造成B[i]，但这次土地排列成环，且不可买进买出，只能运，且∑A[i]=∑B[i]，问最小花费。
INPUT FORMAT: * 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).
题解：显然不用多说，在最优方案中，两个堆之间的移动必然是单向的，不可能出现甲挪到乙，然后又白费力气挪回去的情况，然后算出每个堆最终的移动情况，然后求出前缀和，然后弄出相对于中位数的绝对值之差的和即可
1 var
2 i,j,k,l,m,n:longint;
3 a1,a2,ans:int64;
4 a,b:array[0..200000] of int64;
5 procedure swap(var x,y:int64);
6 var z:int64;
7 begin
8 z:=x;x:=y;y:=z;
9 end;
10 procedure sort(l,r:longint);inline;
11 var i,j:longint;x:int64;
12 begin
13 i:=l;j:=r;x:=b[(l+r) div 2];
14 repeat
15 while b[i]<x do inc(i);
16 while b[j]>x do dec(j);
17 if i<=j then
18 begin
19 swap(b[i],b[j]);
20 inc(i);dec(j);
21 end;
22 until i>j;
23 if i<r then sort(i,r);
24 if l<j then sort(l,j);
25 end;
26 begin
27 readln(n);m:=(n+1) div 2;
28 for i:=1 to n do
29 begin
30 readln(a1,a2);
31 a[i]:=a1-a2;
32 end;
33 for i:=2 to n do b[i]:=a[i-1]+b[i-1];
34 b[1]:=a[n]+b[n]; //A掉后才发现这句话其实完全可以删掉，想想为什么^_^
35 sort(1,n);ans:=0;
36 for i:=1 to n do ans:=ans+abs(b[m]-b[i]);
37 writeln(ans);
38 end.
