BZOJ3293:[CQOI2011]分金币

Description

圆桌上坐着n个人，每人有一定数量的金币，金币总数能被n整除。每个人可以给他左右相邻的人一些金币，最终使得每个人的金币数目相等。你的任务是求出被转手的金币数量的最小值。

Input

第一行为整数n（n>=3），以下n行每行一个正整数，按逆时针顺序给出每个人拥有的金币数。

Output

输出被转手金币数量的最小值。

Sample Input

4
1
2
5
4

Sample Output

4
样例解释
设四个人编号为1,2,3,4。第3个人给第2个人2个金币（变成1,4,3,4），第2个人和第4个人分别给第1个人1个金币。

HINT

N<=100000,总金币数<=10^9

题解：

一道很经典的题目。

用b[i]表示前i个人总共还需要多少金币（即第n人与第1人、第i人与下一个的金币交换情况）。

设第n个人给了第1个人x金币，则第i个人与下一个人的金币流动量为|b[i]-x|。

我们要使∑|b[i]-x|最小，则x应选b的中位数。

代码（P++注意）：

#include <bits/stdc++.h>
using namespace std;
#define begin {
#define end }
#define while while(
#define if if(
#define do )
#define then )
#define for for(
#define fillchar(a,b,c) memset(a,c,b)
#define writeln printf("
")
#define write printf
#define readln readl()
#define inc(a) a++
#define dec(a) a--
#define exit(a) return a
#define mod %
#define div /
#define shl <<
#define shr >>
#define extended long double
#define longint int
#define integer short
#define int64 long long
template<typename T> inline void read(T& a)
begin
  T x=0,f=1; char ch=getchar();
  while(ch<'0')or(ch>'9')do
  begin
    if ch=='-' then f=-1; ch=getchar();
  end
  while(ch>='0')and(ch<='9')do
  begin
    x=x*10+ch-'0'; ch=getchar();
  end
  a=x*f;
end
inline void readl()
begin
  char ch; ch=getchar();
  while ch!='
' do ch=getchar();
end
int64 a[100001],b[100001];
int64 tot,n,m,i;
int64 ans;
int main()
begin
  read(n);
  for i=1;i<=n;i++ do begin read(a[i]); tot=tot+a[i]; end;
  tot=tot div n;
  for i=1;i<=n;i++ do b[i]=b[i-1]+tot-a[i];
  sort(b+1,b+n+1); tot=b[(1+n)div 2];
  for i=1;i<=n;i++ do ans=ans+abs(tot-b[i]);
  write("%lld",ans); writeln;
end