Spreading the Wealth UVA

Spreading the Wealth

题意：n个人坐一圈，每个人x[i]个糖果，且只能给相邻的人糖果，问最少一共给多少个糖果才能使得每个人糖果都一样多。

不看白书真是想不到这么做~

分析见白书P6

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int maxn=1000010;
 5 ll c[maxn];
 6 ll x[maxn];
 7 
 8 int main(){
 9     int n;
10     while(scanf("%d",&n)!=EOF){
11         ll tot=0;
12         for(int i=0;i<n;i++){
13             scanf("%lld",&x[i]);
14             tot+=x[i];
15         }
16         ll m=tot/n;
17         c[0]=0;
18         for(int i=1;i<n;i++) {
19            c[i]=c[i-1]+x[i]-m;
20         }
21         sort(c,c+n);
22         int base=c[n/2];
23         ll res=0;
24         for(int i=0;i<n;i++) res+=abs(base-c[i]);
25         printf("%lld
",res);
26     }
27 }

View Code