贪心+数学

1.显然，代价的计算是一个麻烦的事情.我认为代价的计算应该是与路径有关，而不是与人有关.也就是说，我们关心的是两个人之间的路径上糖果移动的情况，可以设X_i：A_i—>A_i+1为糖果的路径转移

2.发现，一条路径上糖果的移动方向只有一个，可以用正负来表示.接着我们还发现，只要知道了一条路径上糖果的移动情况，那么其他路径也是可以推出来的.

图片来源:CSDN博客

找出递推式 <1>关注的每两个人之间的路径上饺子移动的情况。

<2> 设第i个人会给第i+1个人xi个糖果（带符号）即下图：那么 ai-xi+xi-1=ave;

<3>将所有的式子列出来然后每一个做一个前缀和:那么xn−xi=∑ai−ave。

<5> 变形：xi=xn−(∑ai−ave).((∑ai−ave)为一个常量，简写为k)

<4>找到递推式，要求∑|xi|最小实际上就是要求∑|xn−k|最小 。利用绝对值的几何意义，那么xn取这些常量k里的中位数时，代价有最小值

与上文图片来自同一大佬的公式推导过程:

AC代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,cnt,ans,mid;
ll a[1000100],b[1000100];
int main(){cin>>n;
	for(ll i=1;i<=n;i++)cin>>a[i],cnt+=a[i];//输入糖果数量并计算总和
	cnt/=n;//计算平均值
	for(int i=1;i<=n;i++)b[i]=b[i-1]+(a[i]-cnt);//构造前缀和数组
	sort(b+1,b+n+1);mid=b[(n+1)/2];//排序以找到中位数
	for(int i=1;i<=n;i++)ans+=abs(b[i]+(-mid));//计算最小代价
	cout<<ans;
	return 0;
}