[bzoj1045]糖果传递
用b[i]表示第i个人给第i+1个人（b[n]表示给1，可以为负）的糖果数量，显然有$ai+b_{i-1}-bi=sum_{i=1}^{n}ai/n$
很容易构造出某一组bi（例如确定b1=0），那么我们可以让所有bi加上某个值，然后最小化$sum_{i=1}^{n}|bi|$
当bi中正数个数多于非正数，那么可以通过-1减小答案，反之同理，因此即选择b中的中位数减为0后即答案
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,a[1000005],b[1000005]; 4 long long s,ans; 5 int main(){ 6 scanf("%d",&n); 7 for(int i=0;i<n;i++)scanf("%d",&a[i]); 8 for(int i=0;i<n;i++)s+=a[i]; 9 s/=n; 10 for(int i=1;i<n;i++)b[i]=a[i]+b[i-1]-s; 11 sort(b,b+n); 12 s=b[n/2]; 13 for(int i=0;i<n;i++)ans+=abs(b[i]-s); 14 printf("%lld",ans); 15 }