题目描述

G 公司有 n 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使n个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。
数据保证一定有解。

题目链接：
https://www.acwing.com/problem/content/description/2196/

样例

略

算法1

sum[i]：累计的货物量， avg平均值
假设i-1到i没有货物交换（一定存在这样一个点，请参考lyd书p34，七夕祭，acwing上也有），后面的只能从紧接着的下一个取货，总移动量为：abs(sum[j]-sum[i]-(j-i)avg)的累加（对于j）,这相当于减去前面需要的，再补足不够的。
转换公式为：abs(sum[j]-javg-(sum[i]-iavg)),这相当于在位置于sum[j]-javg的n个地址上选一个做货仓，保证距离之和最小，这就是中位数。

代码很短，速度很快，复杂度n log n（用于排序），求百万级都可以。用这个方法，此题不应是困难级。

最小费用最大流求解它，有点牛刀了。不过对于学习费用流是不错。

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N=110;
int d[N],sum[N],n,avg,ans;

int main(){
    cin>>n;
    int avg=0;
    for(int i=1;i<=n;i++)
        cin>>d[i], avg+=d[i], sum[i]=sum[i-1]+d[i];  
    avg/=n;
    for(int i=1;i<=n;i++)
        sum[i]-=i*avg;
    sort(sum+1,sum+1+n);
    int mid=sum[(n+1)/2];
    for(int i=1;i<=n;i++)
        ans+=abs(sum[i]-mid);
    cout<<ans<<endl;
}

算法2

最小费用最大流, 多的点连S, 少的点连T，相邻的点相互连接

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N=110, M=1100, inf=0x3f3f3f3f;
int ver[M],f[M],w[M],nxt[M],head[N],tot=1;
int d[N],q[N],fx[N],pre[N];
bool inq[N];
int n,S,T;

void add(int a,int b,int c,int d){
    ver[++tot]=b, f[tot]=c, w[tot]= d, nxt[tot]=head[a], head[a]=tot;
    ver[++tot]=a, f[tot]=0, w[tot]=-d, nxt[tot]=head[b], head[b]=tot;
}

bool spfa(){
    memset(d,0x3f,sizeof d);
    fx[T]=0;
    int hh=0, tt=1;
    d[S]=0, q[0]=S, fx[S]=inf;
    while(hh!=tt){
        int t=q[hh++];
        if(hh==N)hh=0;
        inq[t]=false;
        for(int i=head[t];i;i=nxt[i]){
            int y=ver[i];
            if(!f[i] || d[t]+w[i]>=d[y])continue;
            d[y]=d[t]+w[i];
            fx[y]=min(f[i],fx[t]);
            pre[y]=i;
            if(!inq[y]){
                inq[y]=true;
                q[tt++]=y;
                if(tt==N)tt=0;
            }
        }
    }
    return fx[T]>0;
}

void EK(int &flow, int &cost){
    flow=cost=0;
    while(spfa()){
        int t=fx[T];
        flow+=t, cost+=d[T]*t;
        for(int x=T;x!=S;x=ver[pre[x]^1])
            f[pre[x]]-=t, f[pre[x]^1]+=t;
    }
}

int main(){
    cin>>n;
    S=0, T=n+1;
    int avg=0;
    for(int i=1;i<=n;i++)
        cin>>d[i], avg+=d[i];  //此处复用d数组，数据处理完之后，具体数据就没有用
    avg/=n;
    for(int i=1;i<=n;i++){
        add(i, i==n ? 1 : i+1, inf,1);
        add(i, i==1 ? n : i-1, inf,1);
        if(d[i]-avg>0) add(S,i, d[i]-avg,0);
        if(d[i]-avg<0) add(i,T, avg-d[i],0);
    }
    int flow,cost;
    EK(flow,cost);
    cout<<cost<<endl;
}