uva - 11300 - Spreading the Wealth


		——>>设第i个人给了xi个cions自己左边的人：则有
 
——————————————>>x1 = x1 + 0;
 
第1人：a[1] - x1 + x2 = M；——>>x2 = x1 - (a[1]-M)
 
第2人：a[2] - x2 + x3 = M；——>>x3 = x1 - (a[1]-M) - (a[2]-M)
 
……
 
第n-1人：a[n-1] - x(n-1) + xn = M；——>>xn = x1 - (a[1]-M) - (a[2]-M) - ... - (a[n-1]-M)；
 
第n人：a[n] - xn + x1 = M；（这个没用了）
 
设c[i] = c[i-1] + a[i] - M；
 
则有：
 
——>>x1 = x1 + c[0]
 
——>>x2 = x1 - c[1]
 
——>>x3 = x1 - c[2]
 
……
 
——>>x(n-1) = x1 - c[n]；
 
要求的便是| x1 | + | x1 + c[0] | + | x1 - c[1] | + ... + | x1 - c[n] |的最小值——>>中位数！
 
[cpp]  
#include <iostream>  
#include <algorithm>  
#include <cmath>  
  
using namespace std;  
  
const int maxn = 1000001 + 10;  
  
long long a[maxn], c[maxn];     //a[i]为输入的第i个人的初始拥有资金，c[i]为 a[1]-M + a[2]-M + ... + a[i]-M  
  
int main()  
{  
    int n, i;  
    while(cin>>n)  
    {  
        long long sum = 0;      //总和  
        for(i = 1; i <= n; i++)  
        {  
            cin>>a[i];  
            sum += a[i];  
        }  
        long long M = sum / n;      //求每人最后得到的钱  
        c[0] = 0;  
        for(i = 1; i < n; i++)  
            c[i] = c[i-1] + a[i] - M;  
        sort(c, c+n);       //从小到大排序，以便求得中位数  
        long long x1 = c[n/2];     //中位数的下标  
        sum = 0;        //这次用sum来计算总交换的金币数  
        for(i = 0; i < n; i++)  
            sum += abs(x1 - c[i]);  
        cout<<sum<<endl;  
    }  
    return 0;  
}

补充：软件开发 , C++ ,