UVA 11300-Spreading the Wealth(代数解析+距離と最小)

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=33899
タイトル: 
問題:n人は1周して座って、すべての人はいくつかのお金があって、今これらのお金を分けなければならなくて、すべての人はお金を周囲の人にあげることしかできなくて、少なくともいくら移転してやっと分けます
  
考え方:最終的に得られるお金の数はMで、Xiは彼のために前の人にあげたお金で、それではすべての人の最後のお金は:A[I]-Xi+X(i+1)=M
n-1個の公式をリストして、最後にすべてxi用 Xi=X 1-Cで表すと、答えは|X 1|+|X 2|+……+|Xn|=|X 1|+|X 1-C 1|+……+|Xn-C(n-1)| 
そしてCの関係は  Cn=C(n-1) +An -M     ,C[0]=0で全てのCiが求められる
そして
 | X1 |+|X1-C1|+......+|X1-C(n-1) |  
そうです 数軸上のn点からX 1までの距離の和 
上記の距離を最小限に抑えるにはどうすればいいですか?
この点がn個の数の中位数、つまり真ん中の点です
.

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
long long tm[1000006]; 
int main()
{
	
	
	int n,i; 
	while(scanf("%d",&n)!=EOF)
	{
		long long sum=0;	
		for (i=1;i<=n;i++)
		{
			scanf("%lld",&tm[i]);
			sum+=tm[i];
		}
		long long avg=sum/n;
		tm[0]=0;
		for(i=1;i<n;i++)
		{ 
			tm[i]=tm[i-1]+tm[i]-avg;
		}
		sort(tm,tm+n);
		long long x=tm[n/2];
		long long ans=0;
		for (i=0;i<n;i++)
		{
			ans+=abs(tm[i]-x);
		}
		cout<<ans<<endl;  
		
		
	}	
	
	
	
	return 0;
	
}