题意

图片说明

题解

最小费用流。
对于每一个点，考虑达到平衡所需操作，是否需要运出或运入货物。
建图：
设源点s和汇点t.
对于所有需要运出货物的点i，令s与i连边，流量为需要运出的货物数量，费用为0。
对于所有需要运入货物的点j，令j与t连边，流量为需要运入的货物数量，费用为0。
对于相邻两节点，建双向边，流量无穷，费用为1。

这样跑最小费用流
针对每个需要运出的点，都流过了所需运出的货物大小的流量。针对每个需要运入的点，也都流过了所需运入的货物大小的流量。
这样的最大流是固定的，求得的最小费用流最大流，就是题目所需的搬运量。

code

#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(int i=(l);i<(r);i++)
using namespace std;

const int maxn = 200 + 10;
const int mod = 1e9 + 7;

struct Edge{
    int to, cap, cost;
    int nxt;
}edges[maxn * maxn];

int head[maxn],tot;
int vis[maxn],pre[maxn],dis[maxn];

void addedge(int u,int v,int f,int c)
{
    edges[tot] = {v,f,c,head[u]};
    head[u] = tot++;
}

void addedges(int u,int v,int f,int c)
{
    addedge(u,v,f,c);
    addedge(v,u,0,-c);
}

bool spfa(int s,int t)
{
    memset(pre,-1,sizeof(pre));
    fill(dis,dis+maxn,inf);
    memset(vis,0,sizeof(vis));
    queue<int> q;
    vis[s] = 1;
    dis[s] = 0;
    q.push(s);
    while(q.size()){
        int hd = q.front();
        q.pop();
        vis[hd] = 0;
        for(int i = head[hd];~i;i = edges[i].nxt){
            auto &e = edges[i];
            if(e.cap > 0 && dis[e.to] > dis[hd] + e.cost){
                dis[e.to] = dis[hd] + e.cost;
                pre[e.to] = i;
                if(!vis[e.to]){
                    vis[e.to] = 1;
                    q.push(e.to);
                }
            }
        }
    }
    return ~pre[t];

}

int mcmf(int s,int t){
    int flow = 0;
    int cost = 0;
    while(spfa(s,t)){
        int mf= inf;
        for(int i = pre[t];~i;i = pre[edges[i^1].to]){
            mf = min(mf,edges[i].cap);
        }
        flow += mf;
        for(int i = pre[t];~i;i = pre[edges[i^1].to]){
            edges[i].cap -= mf;
            edges[i^1].cap += mf;
            cost += mf * edges[i].cost;
        }
    }
    return cost;
}

int a[maxn];

int main()
{
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
    int s = 0,t = maxn - 1;
    tot = 0;
    memset(head,-1,sizeof(head));
    int n;
    cin>>n;
    int sum = 0;
    for(int i = 1;i <= n;++i){
        cin>>a[i];
        sum += a[i];
    }
    sum /= n;
    for(int i = 1;i <= n;++i){
        a[i] = a[i] - sum;
    }

    for(int i = 1;i <= n;++i){
        if(a[i] > 0) addedges(s,i,a[i],0);
        else if(a[i] < 0) addedges(i,t,-a[i],0);
    }
    for(int i = 2;i <= n;++i){
        addedges(i,i-1,inf,1);
        addedges(i-1,i,inf,1);
    }
    addedges(1,n,inf,1);
    addedges(n,1,inf,1);
    int c = mcmf(s,t);
    printf("%d\n",c);

   return 0;
}