%%%hzwdalao

「问题分析」

转化为供求平衡问题，用最小费用最大流解决。

「建模方法」

首先求出所有仓库存货量平均值，设第i个仓库的盈余量为A[i]，A[i] = 第i个仓库原有存货量 – 平均存货量。建立二分图，把每个仓库抽象为两个节点Xi和Yi。增设附加源S汇T。

1、如果A[i]>0，从S向Xi连一条容量为A[i]，费用为0的有向边。
2、如果A[i]<0，从Yi向T连一条容量为-A[i]，费用为0的有向边。
3、每个Xi向两个相邻顶点j，从Xi到Xj连接一条容量为无穷大，费用为1的有向边，从Xi到Yj连接一条容量为无穷大，费用为1的有向边。

求最小费用最大流，最小费用流值就是最少搬运量。

「建模分析」

计算出每个仓库的盈余后，可以把问题转化为供求问题。建立供求网络，把二分图X集合中所有节点看做供应节点，Y集合所有节点看做需求节点，在能一次搬运满足供需的Xi和Yj之间连接一条费用为1的有向边，表示搬运一个单位货物费用为1。另外还要在Xi与相邻的Xj之间连接边，表示货物可以暂时搬运过去，不立即满足需求，费用也为1。最大流满足了所有的盈余和亏损供求平衡，最小费用就是最少搬运量。

#include <bits/stdc++.h>
#define N 1000003
#define MAX 0x3f3f3f3f
using namespace std;
int head[N],deep[N],pre[N],dis[N],minn[N];
int st,ed,cnt,n,m,sum,flag[N],ans_flow,ans_cost,a[N];
struct node
{
    int to,w,fr,cost;
    int next=-1;
}edge[N];

inline void add(int u, int v, int k,int cc) {
    edge[cnt].fr = u, edge[cnt].to = v, edge[cnt].w = k;edge[cnt].cost=cc;
    edge[cnt].next = head[u], head[u] = cnt++;
    edge[cnt].fr = v, edge[cnt].to = u, edge[cnt].w = 0;edge[cnt].cost=-cc;
    edge[cnt].next = head[v], head[v] = cnt++;
}

bool SPFA(int s,int t)
{
    queue<int> q;
    memset(flag,0,sizeof(flag));
    memset(pre,-1,sizeof(pre));
    memset(dis,MAX,sizeof(dis));
    q.push(s);
    flag[s]=1;
    dis[s]=0;
    minn[s]=MAX;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        flag[u]=0;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int kk=edge[i].to;
            if(edge[i].w>0&&dis[kk]>dis[u]+edge[i].cost)
            {
                dis[kk]=dis[u]+edge[i].cost;
                minn[kk]=min(edge[i].w,minn[u]);
                pre[kk]=i;
                if(!flag[kk])
                {
                    q.push(kk);
                    flag[kk]=1;

                }
            }

        }
    }
    if(dis[t]!=MAX)return 1;
    else return 0;

}
void dfs(int s,int t)
{
    int x=t;
    while(x!=s)
    {
        int i=pre[x];
        edge[i].w-=minn[t];
        edge[i^1].w+=minn[t];
        x=edge[i^1].to;
    }
    ans_flow+=minn[t];
    ans_cost+=dis[t]*minn[t];


}
void EK()
{
    while(SPFA(st,ed))
      dfs(st,ed);
}
int c(int x,int y){return x*2-1+y;}//xi=c(x,0)供应  yi=c(x,1)需求

int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    st=0;ed=500;
    for(int i=1;i<=n;i++)
    {

        scanf("%d",&a[i]);
        sum+=a[i];
    }
    sum=sum/n;
    for(int i=1;i<=n;i++)a[i]-=sum;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>0)add(st,c(i,0),a[i],0);//需供应
        else add(c(i,1),ed,-a[i],0);//不满则需求
    }
    for(int i=1;i<=n;i++)
    {
        if(i!=n)
        {
            add(c(i,0),c(i+1,1),MAX,1);//运货消费为1
            add(c(i,0),c(i+1,0),MAX,1);//中转站费用为1
        }
        if(i!=1)
        {
            add(c(i,0),c(i-1,1),MAX,1);
            add(c(i,0),c(i-1,0),MAX,1);
        }

    }
    add(c(n,0),c(1,0),MAX,1);//首尾连边
    add(c(n,0),c(1,1),MAX,1);
    add(c(1,0),c(n,1),MAX,1);
    add(c(1,0),c(n,0),MAX,1);
    EK();
    printf("%d",ans_cost);


    return 0;
}