uva 11300

题目大意：

 

分析：因为题目给出的是一个环，我们从第一个位置开始考虑，假设每个位置都要给它左边金币并且接受右边的金币，位置2给位置1金币数为x2,位置2接收的金币为x3，我们将位置2列出等式有：(M为每个位置的目标金币，A2为位置2的原始金币)，由上可以列出每个位置的等式：。根据每个位置可以解出n-1个关于x1的等式Xi也可以，因为最后目标是最小化转手金币，则每个位置转移的金币为,最小化这个式子就可以了得出答案。

 

---

#include <bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
typedef long long ll;
ll a[maxn],n,c[maxn];
int main(){
    while(~scanf("%d",&n)){
        ll tot=0;
        for(int i=0;i<n;i++){
            cin>>a[i];tot+=a[i];
        }
        c[0]=0;
        ll M=tot/n;
        for(int i=1;i<n;i++)c[i]=c[i-1]+M-a[i-1];
        sort(c,c+n);
        ll x=c[n/2],ans=0;
        for(int i=0;i<n;i++)ans+=abs(x-c[i]);
        cout<<ans<<endl;
    }
    return 0;
}