分金币（Spreading the Wealth，UVa 11300,中位數）

題目連結

https://vjudge.net/problem/UVA-11300

題目

A Communist regime is trying to redistribute wealth in a village. They have have decided to sit everyone

around a circular table. First, everyone has converted all of their properties to coins of equal value,

such that the total number of coins is divisible by the number of people in the village. Finally, each

person gives a number of coins to the person on his right and a number coins to the person on his left,

such that in the end, everyone has the same number of coins. Given the number of coins of each person,

compute the minimum number of coins that must be transferred using this method so that everyone

has the same number of coins.

Input

There is a number of inputs. Each input begins with n (n < 1000001), the number of people in the

village. n lines follow, giving the number of coins of each person in the village, in counterclockwise

order around the table. The total number of coins will fit inside an unsigned 64 bit integer.

Output

For each input, output the minimum number of coins that must be transferred on a single line.

Sample Input

3

100

100

100

4

1

2

5

4

Sample Output

4

題意

圓桌旁坐着n個人，每個人有一定數量的金币a[i]，金币總數能被n整除。每個人可以給他左右相鄰的人一些金币，最終使得每個人的金币數目相等。你的任務是求出被轉手的金币的數量的最小值。

題解

每個人隻會與左右相鄰的人進行互動，即一共進行n次互動。而A給B兩個金币，B給A四個金币等價于B給A兩個金币，是以倆人的互動可以用一個值x[i]來表示。問題轉化為求n個xi的值之和的最小值。

設x[i]表示第i個人給第i-1個人的金币的數量，如果x[i]為負，說明第i個人從第i-1個那拿了x[i]個金币。

因為最終每個人的金币為是以金币數量的平均值（設為m），是以a[i]-x[i]+x[i+1]=m.

又因為前n-1個人的金币互動完成之後，第

n個人的金币互動就随之确定下來了，是以有效的方程組隻有n-1個，也就是說無法根據n-1個方程解n個未知量。

雖然無法解出n個未知量，但是可以統一用一個未知量去表示其他n-1個未知量，即

x[2]=m-a[1]+x[1];

x[3]=m-a[2]+(m-a[1]+x[1])=2m

…

而除x[1]以外的量都是常量，可以用c[i]來表示。

注意到，c[i]=c[i-1]+a[i]-m.

是以x[i]=|x[1]-c[i]|,即x[i]的幾何意義為x[1]與c[i]的距離。求n個xi的值的最小值轉化成求一點到數軸上n個點的距離之和的最小值。

上述問題的最優解為：n個點的中位數到n個點的距離之和最小。

代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long ll;
const int maxn=+;
ll a[maxn],tot,c[maxn];

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(c,,sizeof(c));
        tot=;
        for(int i=;i<n;i++)
        {
            scanf("%lld",&a[i]);
            tot+=a[i];
        }
        long long m=tot/n;
        c[]=;
        for(int i=;i<=n-;i++)
            c[i]=c[i-]+a[i]-m;
        sort(c,c+n-);
        long long x1=c[(n-)/];
        tot=;
        for(int i=;i<n;i++)
            tot+=abs(x1-c[i]);
        printf("%lld\n",tot);
    }
}