P1368 均分纸牌（加强版）
题目描述
有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，纸牌总数必为 N 的倍数。可以在任一堆上取1张纸牌，然后移动。
移牌规则为：在编号为 1 堆上取的纸牌，能移到编号为 2和N 的堆上；在编号为 N 的堆上取的纸牌，能移到编号为 N-1和1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法，使每堆上纸牌数都一样多且牌的移动次数尽量少。
输入输出格式
输入格式：
第一行一个整数n
第二行为n个空格分开的正整数，为n堆纸牌的牌数。
输出格式：
只有一个数，为最少的移动次数。
输入输出样例
输入样例#1：
4
1 2 5 4
输出样例#1：
4
说明
对样例的说明：
①第4堆移动1张牌至第1堆
②第3堆移动1张牌至第2堆
③第3堆移动1张牌至第2堆
④第2堆移动1张牌至第1堆
此时移动次数为4最小
【数据范围】
对于40%的数据，n<=10000
对于100%的数据，n<=1000000，所有纸牌数总和在2147483647内
/*
设平均数为xba 不妨设a1给了an x1 张纸牌（k可正可负），a2给了a1 x2张纸牌， a3给了a2 x3 张纸牌……an给了a(n - 1) xn张纸牌，不难发现以下方程： xba = a1 - x1 + x2
xba = a2 - x2 + x3
xba = a3 - x3 + x4
xba = a4 - x4 + x5
......
xba = a(n - 1) - x(n - 1) + xn
xba = an - xn + x1 我们考虑最终结果，应该是
|x1| + |x2| + |x3| + .... + |xn| 换元法，得到
ans = |x1| + |xba - a1 + x1| + |2xba -a1 - a2 + x1| + |3xba -a1 - a2 - a3 + x1| + ..... + |(n - 1)xba - Σai,i <= n - 1|转换为一次函数带绝对值的最值问题 数形结合思想，看做是数轴上点的距离。
中位数时距离和最小。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 1000010
#define INF 0x3f3f3f3f
long long a[maxn],sum,f[maxn],xba,n,k,ans;
int main(){
scanf("%d",&n);
for(long long i=;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
xba=sum/n;
f[]=;
for(long long i=;i<=n;i++)
f[i]=f[i-]+xba-a[i-];
sort(f+,f+n+);
k=f[n/+];
for(long long i=;i<=n;i++)
ans+=abs(k-f[i]);
cout<<ans;
return ;
}