#include<bits/stdc++.h>
using namespace std;
const int maxn=100;
struct edg
{
	int c,nxt,t;
	double w;
}e[maxn+1<<3||2];
int cnt,fst[maxn+10],i,n,s=1,t;
bool bz[maxn+10];
double sumn,tmp,tot;
long long a[maxn+10],dis[maxn+10];
queue<int>q;
void ad(int u,int v,double w,int c)
{
	e[cnt].t=v;
	e[cnt].w=w;
	e[cnt].c=c;
	e[cnt].nxt=fst[u];
	fst[u]=cnt++;
	return;
}
bool spf(int x)
{
	int i,y;
	memset(bz,true,sizeof(bz));
	memset(dis,127,sizeof(dis));
	q.push(x);
	dis[x]=bz[x]=0;
	while(q.size())
	{
		y=q.front();
		q.pop();
		bz[y]=true;
		for(i=fst[y];~i;i=e[i].nxt)
		{
			if(e[i].w!=0&&dis[e[i].t]>dis[y]+e[i].c)
			{
				dis[e[i].t]=dis[y]+e[i].c;
				if(bz[e[i].t])
				{
					q.push(e[i].t);
					bz[e[i].t]=false;
				}
			}
		}
	}
	return dis[t]!=0x7f7f7f7f7f7f7f7f;
}
double dfs(int x,double mn)
{
	int i;
	double ans=0,sumn=0,tmp;
	if(x==t)
		return mn;
	bz[x]=false;
	for(i=fst[x];~i;i=e[i].nxt)
	{
		if(bz[e[i].t]&&e[i].w!=0.0&&dis[e[i].t]==dis[x]+e[i].c)
		{
			tmp=dfs(e[i].t,min(mn-ans,e[i].w));
			e[i].w-=tmp;
			e[i^1].w+=tmp;
			ans+=tmp;
			sumn+=tmp*e[i].c;
		}
	}
	bz[x]=true;
	return sumn;
}
int main()
{
	scanf("%d",&n);
	t=n+2;
	memset(fst,-1,sizeof(fst));
	for(i=1;i<=n;++i)
	{
		scanf("%lld",&a[i]);
		tot+=a[i];
		ad(1,i+1,a[i],0);
		ad(i+1,1,0,0);
	}
	tot/=n;
	for(i=1;i<=n;++i)
	{
		ad(i,i%n+1,1.0*LLONG_MAX,1);
		ad(i%n+1,i,0,-1);
		ad(i%n+1,i,1.0*LLONG_MAX,1);
		ad(i,i%n+1,0,-1);
	}
	for(i=1;i<=n;++i)
	{
		ad(i+1,n+2,tot,0);
		ad(n+2,i+1,0,0);
	}
	while(spf(s))
	{
		memset(bz,true,sizeof(bz));
		while(tmp=dfs(s,1.0*LLONG_MAX))
			sumn+=tmp;
	}
	printf("%g",sumn);
	return 0;
}

输出：

0

悬赏三个关注