题意：
思路：
【问题分析】
转化为供求平衡问题，用最小费用最大流解决。
【建模方法】
首先求出所有仓库存货量平均值，设第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。最大流满足了所有的盈余和亏损供求平衡，最小费用就是最少
搬运量。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef unsigned int uint; 5 typedef unsigned long long ull; 6 typedef long double ld; 7 typedef pair<int,int> PII; 8 typedef pair<ll,ll> Pll; 9 typedef vector<int> VI; 10 typedef vector<PII> VII; 11 typedef pair<ll,ll>P; 12 #define N 50000 13 #define M 1000000 14 #define INF 1e9 15 #define fi first 16 #define se second 17 #define MP make_pair 18 #define pb push_back 19 #define pi acos(-1) 20 #define mem(a,b) memset(a,b,sizeof(a)) 21 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++) 22 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--) 23 #define lowbit(x) x&(-x) 24 #define Rand (rand()*(1<<16)+rand()) 25 #define id(x) ((x)<=B?(x):m-n/(x)+1) 26 #define ls p<<1 27 #define rs p<<1|1 28 29 const ll MOD=1e9+7,inv2=(MOD+1)/2; 30 double eps=1e-6; 31 int dx[4]={-1,1,0,0}; 32 int dy[4]={0,0,-1,1}; 33 34 int head[N],vet[N],nxt[N],len1[N],len2[N],dis[N],inq[N],a[N],q[N],pre[N][2],num[N][2], 35 s,S,T,ans1,ans2,tot; 36 37 int read() 38 { 39 int v=0,f=1; 40 char c=getchar(); 41 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 42 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 43 return v*f; 44 } 45 46 void add(int a,int b,int c,int d) 47 { 48 nxt[++tot]=head[a]; 49 vet[tot]=b; 50 len1[tot]=c; 51 len2[tot]=d; 52 head[a]=tot; 53 54 nxt[++tot]=head[b]; 55 vet[tot]=a; 56 len1[tot]=0; 57 len2[tot]=-d; 58 head[b]=tot; 59 } 60 61 int spfa() 62 { 63 rep(i,1,s) 64 { 65 dis[i]=INF; 66 inq[i]=0; 67 } 68 int t=0,w=1; 69 q[1]=S; dis[S]=0; inq[S]=1; 70 while(t<w) 71 { 72 t++; int u=q[t%(s+5)]; inq[u]=0; 73 int e=head[u]; 74 while(e) 75 { 76 int v=vet[e]; 77 if(len1[e]&&dis[u]+len2[e]<dis[v]) 78 { 79 dis[v]=dis[u]+len2[e]; 80 pre[v][0]=u; 81 pre[v][1]=e; 82 if(!inq[v]) 83 { 84 w++; q[w%(s+5)]=v; inq[v]=1; 85 } 86 } 87 e=nxt[e]; 88 } 89 } 90 if(dis[T]==INF) return 0; 91 return 1; 92 } 93 94 void mcf() 95 { 96 int k=T,t=INF; 97 while(k!=S) 98 { 99 int e=pre[k][1]; 100 t=min(t,len1[e]); 101 k=pre[k][0]; 102 } 103 ans1+=t; 104 k=T; 105 while(k!=S) 106 { 107 int e=pre[k][1]; 108 len1[e]-=t; 109 len1[e^1]+=t; 110 ans2+=t*len2[e]; 111 k=pre[k][0]; 112 } 113 114 } 115 116 int main() 117 { 118 //freopen("1.in","r",stdin); 119 int n=read(); 120 int sum=0; 121 rep(i,1,n) 122 { 123 a[i]=read(); 124 sum+=a[i]; 125 } 126 s=0; 127 rep(i,1,n) 128 rep(j,0,1) num[i][j]=++s; 129 int avg=sum/n; 130 S=++s,T=++s; 131 rep(i,1,s) head[i]=0; 132 tot=1; 133 rep(i,1,n) 134 { 135 if(a[i]>avg) add(S,num[i][0],a[i]-avg,0); 136 if(a[i]<avg) add(num[i][1],T,avg-a[i],0); 137 } 138 rep(i,1,n) 139 { 140 int x=i-1; 141 if(x==0) x=n; 142 add(num[i][0],num[x][0],INF,1); 143 add(num[i][0],num[x][1],INF,1); 144 x=i+1; 145 if(x==n+1) x=1; 146 add(num[i][0],num[x][0],INF,1); 147 add(num[i][0],num[x][1],INF,1); 148 } 149 ans1=ans2=0; 150 while(spfa()) mcf(); 151 printf("%d ",ans2); 152 return 0; 153 154 }