CH0807 糖果传递（均分纸牌问题，前缀和）

描述

有n个小朋友坐成一圈，每人有a[i]个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。求使所有人获得均等糖果的最小代价。

输入格式

第一行一个正整数n<=1000000，表示小朋友的个数。接下来n行，每行一个整数a[i]，表示第i个小朋友初始得到的糖果的颗数．

输出格式

一个整数，表示答案。

样例输入

4
1
2
5
4

样例输出

4

题解：就是一个均分纸牌问题，该问题一般先验证是否整除，然后每个都减取平均数，再得前缀和，最后推导公式累加答案。
对于不成环得均分纸牌问题，一般有公式

若是环形，则与货仓选址结合，得出公式：,其中s[k]为排序后得出得中位数

//#include<bits/stdc++.h>
#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

const int maxn = 1e6+5;

ll a[maxn],s[maxn];

int main(){
	ll n, sum=0;
	cin>>n;
	rep(i,1,n){
		cin>>a[i];
		sum+=a[i];
	}
	s[0]=0;
	rep(i,1,n){
		a[i]-=sum/n;
		s[i]=s[i-1]+a[i];
	}
	sort(s+1,s+n+1); 
	ll k=(n+1)/2;
	sum=0;
	rep(i,1,n){
		sum+=abs(s[i]-s[k]);
	}
	cout<<sum;
	return 0;
}