题意：中文题
思路：就是直接建图跑费用流，每个点和源点连一个r[i]的容量，0费用的边，和汇点连一个平均值，费用为0的点，然后左右连一下边
代码：（商务鞋竟然连样例都没跑不出来，难道最近rp没了么）
#include <bits/stdc++.h> using namespace std; typedef long long LL; inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct Min_cost_flow { int S,T; int ans=0; int vis[100010],vis2[100010]; int d[100010],head[100010],to[100010],nextt[100010],w[100010],cost[100010]; int tot = 2; int inf=0x7fffffff; void init(int _s,int _t) { S=_s;T=_t; memset(head,0,sizeof(head)); ans=0;tot=2; } void add(int u,int v,int cap,int co) { cost[tot]=co; w[tot]=cap; to[tot]=v; nextt[tot]=head[u]; head[u]=tot++; cost[tot] = -co; w[tot]=0; to[tot]=u; nextt[tot]=head[v]; head[v]=tot++; } bool spfa() { memset(vis,0,sizeof(vis)); memset(vis2,0,sizeof(vis2)); for(int i = 1;i<=T;i++)d[i]=inf; queue<int> q; q.push(S); d[S]=0; vis[S]=1; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i = head[u];i;i=nextt[i]) { int v = to[i]; if(w[i] && d[v]>d[u]+cost[i]) { d[v]=d[u]+cost[i]; if(!vis[v]) { vis[v]=1; q.push(v); } } } } return d[T]<inf; } int dfs(int u,int f) { if(u==T) { ans+=d[u] * f; return f; } int res=0; vis2[u]=1; for(int i=head[u];i;i=nextt[i]) { int v = to[i]; if (w[i] && !vis2[v] && d[v]==d[u]+cost[i]) { int temp=dfs(v,min(f-res,w[i])); w[i] -= temp; w[i^1] += temp; res += temp; if(res == f)return res; } } return res; } int MCMF() { while(spfa())dfs(S,inf); return ans; } }mcmf; const int INF=0x3f3f3f3f; int a[105]; int main() { int n=read(); for(int i=1;i<=n;i++)a[i]=read(); int s=0,t=n+1; mcmf.init(s,t); int res=0; for(int i=1;i<=n;i++)res+=a[i]; res/=n; for(int i=1;i<=n;i++){ mcmf.add(s,i,a[i],0); mcmf.add(i,t,res,0); } for(int i=2;i<n;i++){ mcmf.add(i,i-1,INF,1); mcmf.add(i,i+1,INF,1); } mcmf.add(1,2,INF,1);mcmf.add(1,n,INF,1); mcmf.add(n,n-1,INF,1);mcmf.add(n,1,INF,1); printf("%d ",mcmf.MCMF()); return 0; }