BZOJ 1045 糖果传递

***有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。
样例：
Sample Input
        4
        1 2 5 4
Sample Output
        4***

这道题画出图来，你可以发现，其实问题简化成了一个人分别从左右两边得到和送出一些糖果。当然，为
了简化问题的复杂度，可以直接将分糖果定义为单项，不同之处在于这样送出糖果的数量可以为负。
如下图：
通过观察可以发现为了让每个人的糖果分的一样多，那么就如点1，a[1]-X1+X5=average。而我们最后的答案
显然就是|X1|+|X2||+······+|Xn|。其实我们可以假设点1需要（分发）糖果都来自点5，那么这样下去我们可以得
到一组特殊的解，就拿样例来说吧，就如下图：

我们的最终解就是给这几个数加上一个同时加上一个数（不改变上面等式的性质），而要如何才能让这几个数
的绝对值之和最小呢？其实加上一个常量就相当于求这几个数到这个常量的距离的最小值。高中不等式将会告
诉我们，画个数轴理解一下：

根据图像或者解不等式可以得到中间两个数之间这一段得到的距离之和是最小的，那么这个点显然就是这串数
据的中位数了（上图红标）。所以我们直接实现代码就可以了：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
ll a[1000010],b[1000010],mid,ans,average,n;
int main()
{
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        average+=a[i];
    }
    average/=n;
    for(ll i=1;i<=n;i++)
        b[i]=b[i-1]+a[i]-average;
    sort(b+1,b+1+n);
    ll temp=b[n/2],ans=0;
    for(ll i=1;i<=n;i++)
        ans+=abs(b[i]-temp);
    printf("%lld",ans);

    return 0;
}

代码虽简单，但是分析确实有点麻烦。希望对大家有帮助吧！