uva - 11300 - Spreading the Wealth（數學推導，中位數）

題意：劉汝佳大大的例題，分金子。

方法：首先推導出公式例如A1 - x1 + x2 = M，然後根據公式把每個人金幣的變化表示出來，例如x2 = x1 - C，C = A1 - M（M是最後每個人應該有的金幣數，也就是平均數）。 x3 = x1 - C，不過C變化成A1 + A2 - 2M。依次推出C就好。然後就變成了求x1到各個C的距離，用中位數解決。

注意：因為看的例題，所以用long long。但是輸入金幣的時候沒感覺要用 long long。。【後來測試A數組可以用int，C數組也可以，沒測試tot，估計是不行】。

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   

using namespace std;

#define MAX 1000000+10

long long A[MAX], C[MAX], tot, aver, n, sum;

void Input()
{
	int i = 0;
	for (i = 0; i < n; i++)
	{
		cin >> A[i];
		tot += A[i];
	}
}

void Creat_C()
{
	int i = 0;
	C[0] = 0;
	for (i = 1; i < n; i++)
		C[i] = C[i-1] + A[i] - aver;
}

void Calculate()
{
	int i = 0;
	long long mid = C[n/2];
	for (i = 0; i < n; i++)
		sum += abs(C[i] - mid);
}

int main()  
{  
#ifdef Local    
	freopen("a.in", "r", stdin);    
#endif
	int i = 0, j = 0;
	while (cin >> n)
	{
		memset(A, 0, sizeof(A)), memset(C, 0, sizeof(C));
		sum = 0, tot = 0;
		Input();
		aver = tot/n;
		Creat_C();
		sort(C, C+n);
		Calculate();
		cout << sum << endl;
	}
}