uva11130

分金币
题意：圆桌上有n个人，每人有若干金币，金币总和能整除n，每个人可以分给他相邻两个人若干金币，现在需要使每个人最终金币数量相同，求需要转移的金币数量总和的最小值。
类型：单变量极值->中位数问题

代码

#include <stdio.h>

#include <iostream>
using namespace std;
const int maxn = 1000000 + 10;
long long a[maxn], c[maxn], tot, m;
int main(){
    int n;
    while(scanf("%d", &n)!=EOF){
        tot = 0;
        int i, j;
        for(i=1; i<=n; i++){
            scanf("%lld", a+i);
            tot += a[i];
        }
        m = tot / n;
        c[0] = 0;
        for(i=1; i
            c[i] = c[i-1] + a[i] - m;
        sort(c, c+n);
        long long x1 = c[n/2];
        long long ans = 0;
        for(i=0; i
            ans += abs(x1 - c[i]);
        printf("%lld\n", ans);
    }
    return 0;
}