uva 11300 - Spreading the Wealth

点击打开链接uva 11300

思路：数学分析+贪心
分析：
1 首先最终每个人的金币数量可以计算出来，它等于金币总数除以人数n。接下来我们用m来表示每人的最终的金币数
2 现在假设编号为i的人初始化为Ai枚金币，Xi表示第i个人给第i-1个人Xi枚金币，对于第一个人来说他是给第n个人。
3 根据第二点可以知道 则C0 = 0
对于第一个人 A1-X1+X2 = m X2 = m-A1+X1 = X1-C1(规定C1 = A1-m,一下类似) 则C1 = C0+A1-m
对于第二个人 A2-X2+X3 = m X3 = m-A2+X2 = 2m-A1-A2+X1 = X1-C2 则C2 = -2m+A1+A2 = C1+A2-m
...
对于第n个人 An-Xn+X1 = m Xn = m-An+Xn = X1-Cn 则Cn = Cn-1+An-m
那么根据题目ans = X1+X2+X3+...+Xn = X1+X1-C1+X1-C2+...+Xn-Cn。那么如果ans要最小，根据数轴X1-Cn表示的是点X1到点Cn的距离，那么ans要最小就是使得X1为这些点的“中位数”，我们只要找到C数组并且找到中位数即可。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long int64;
const int MAXN = 1000010;
int64 C[MAXN] , A[MAXN];

int main(){
    int n;
    while(scanf("%d" , &n) != EOF){
        int64 sum;
        sum = 0;
        for(int i = 0 ; i < n ; i++){
           scanf("%lld" , &A[i]);
           sum += A[i];
        }
        int64 m = sum/n;//求出每个人最后的金币数
        C[0] = 0;//C[0]为0
        for(int i = 1 ; i < n ; i++)
           C[i] = C[i-1]+A[i]-m;//求C数组
        sort(C , C+n);
        int64 mid;
        if(n%2 == 0)//偶数
          mid = (C[n/2]+C[n/2-1])>>1;
        else
          mid = C[n/2];
        int64 ans = 0;
        for(int i = 0 ; i < n ; i++)
          ans += abs(mid-C[i]);
        printf("%lld\n" , ans);
    }
    return 0;
}