记录编号	277104	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 负载平衡	最终得分	100
用户昵称	prefect1999	是否通过	通过
代码语言	C++	运行时间	0.032 s
提交时间	2016-07-04 19:19:28	内存使用	0.32 MiB

/*
最小费用流：
相邻的仓库之间连双向边，容量无穷大，费用为1。
如果仓库i中的货物小于平均值，则从i向汇点连边（表示i需要接收货物），容量为average - A[i]。
如果仓库i中的货物大于平均值，则从源点向i连边（表示i可以输出货物），容量为A[i] - average。
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
using namespace std;
const int maxn = 210;
const int inf = 1 << 30;
struct edge
{
	int from, to, cap, flow, cost;
	edge(int u, int v, int c, int f, int w) : from(u), to(v), cap(c), flow(f), cost(w){}
};
struct MCMF
{
	int n, m;
	vector<edge> edges;
	vector<int> G[maxn];
	int inq[maxn];
	int d[maxn];
	int p[maxn];
	int a[maxn];
	void init(int n)
	{
		this->n = n;
		for (int i = 0; i < n; ++i)
			G[i].clear();
		edges.clear();
	}
	void add_edge(int from, int to, int cap, int cost)
	{
		edges.push_back(edge(from, to, cap, 0, cost));
		edges.push_back(edge(to, from, 0, 0, -cost));
		m = edges.size();
		G[from].push_back(m - 2);
		G[to].push_back(m - 1);
	}
	bool BellmanFord(int s, int t, int &flow, long long &cost)
	{
		for (int i = 0; i < n; ++i)
			d[i] = inf;
		memset(inq, 0, sizeof(inq));
		d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = inf;
		queue<int> Q;
		Q.push(s);
		while (!Q.empty())
		{
			int u = Q.front(); Q.pop();
			inq[u] = false;
			for (int i = 0; i < (int)G[u].size(); ++i)
			{
				edge &e = edges[G[u][i]];
				if (e.cap > e.flow && d[e.to] > d[u] + e.cost)
				{
					d[e.to] = d[u] + e.cost;
					p[e.to] = G[u][i];
					a[e.to] = min(a[u], e.cap - e.flow);
					if (!inq[e.to])
					{
						Q.push(e.to);
						inq[e.to] = true;
					}
				}
			}
		}
		if (d[t] == inf)
			return false;
		flow += a[t];
		cost += (long long)d[t] * (long long)a[t];
		for (int u = t; u != s; u = edges[p[u]].from)
		{
			edges[p[u]].flow += a[t];
			edges[p[u]^1].flow -= a[t];
		}
		return true;
	}
	int solve(int s, int t, long long &cost)
	{
		int flow = 0; cost = 0;
		while (BellmanFord(s, t, flow, cost));
		return flow;
	}
}mcmf;
int A[maxn], n;
int main()
{
	freopen("overload.in", "r", stdin);
	freopen("overload.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%d", &A[i]);
	int ave = accumulate(A, A + n, 0) / n;
	const int s = n + 1, t = n + 2;
	mcmf.init(n + 5);
	for (int i = 0; i < n; ++i)
	{
		int j = (i + 1) % n;
		int k = (i + n - 1) % n;
		mcmf.add_edge(i, j, inf, 1);
		mcmf.add_edge(i, k, inf, 1);
		if (A[i] > ave)
			mcmf.add_edge(s, i, A[i] - ave, 0);
		else if (A[i] < ave)
			mcmf.add_edge(i, t, ave - A[i], 0);
	}
	long long cost = 0;
	mcmf.solve(s, t, cost);
	printf("%d\n", (int)cost);
	return 0;
}