有n个小朋友，每个小朋友有一些糖果，每次把一个糖果传给左边或者右边的人花费代价1，求每个人糖果数量相同的最小代价。
数据范围.....原题是这样的：
我看了直接就被吓到了.....这直接把1/6个地球，中国的大部分都搬过来了啊.....
然后看了看discuss，n<=10^6
..........
题解：解法非常的妙...
首先每个人最后的糖果是确定的，假设是m
那么设xi为第i-1个人给第i个人的糖果数量（可以是负数），可以得到n个方程
a1 - x1 + x2 = m -> x2=m-a1+x1
a2 - x2 + x3 = m -> x3=m-a2+x2 ->x3=2m-a2-a1+x1
另ci=ai - m
x2=x1-c1
x3=x1-c1-c2
...
所以把c前缀合一下，
x2=x1-c1,
x3=x1-c2.....
答案就是|x1|+|x1-c1|+|x1-c2|.....+|x1-cn|
所以这就是一个只关于一个未知数的最值方程，可以看作数轴上的n个点，要让答案最小，选择中位数就可以啦
#include<cstdio> #include<algorithm> using namespace std; int n,ave,a[1000005];long long sum=0,ans=0,c[1000005]; inline int abs(int x){return x<0?-x:x;} int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i];ave=sum/n; for(int i=1;i<=n;i++)c[i]=c[i-1]+a[i]-ave;sort(c+1,c+n+1); sum=c[(n+1)>>1];for(int i=1;i<=n;i++)ans+=abs(c[i]-sum); printf("%lld",ans); return 0; }