题目描述
G 公司有 n 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 n个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。
输入输出格式
输入格式：文件的第 1 行中有 1 个正整数 n ，表示有 n 个仓库。
第 2 行中有 n 个正整数，表示 n 个仓库的库存量。
输出格式：输出最少搬运量。
输入输出样例
5
17 9 14 16 4
11
说明
1≤n≤100
Solution：
本题巨说是一道网络流的题目，可我不知道咋建模啊！
但是这题，显然更像做过的环形均分纸牌问题，于是贪心直接过了。
先来讲下普通均分纸牌问题：
普通均分纸牌问题就是$n$个小朋友排成一列，各自有$a[i]$张牌，每个人只能给相邻的人传递纸牌，问至少需要传递多少张纸牌才能使每个小朋友牌的个数相等。
设总牌数为$sum$（即$sum=sum{a[i]}$），则每个人最后会各自有$T=frac{sum}{n}$张牌，设$g[i]=T-a[i]$，则让前$k$个人牌数相同需要的交换牌数为$sum_limits{i=1}^{ileq k}{|s[i]|}$，其中$s[i]=sum_limits{j=1}^{jleq i}{g[i]}$，可以这样理解，要让前$k$个人牌数相同，要依次让前$1,2,3…k-1$个人牌数相同，多退少补，会与后边的人发生二者之差绝对值的牌数交换。所以移动总牌数$ans=sum{|s[i]|}$。
再来讲下本题的环形均分纸牌问题：
环形均分纸牌问题就是$n$个小朋友围成了一圈（等同于第一人和最后一人相邻），这样的话其实可以同样的处理。
仔细思考环形均分纸牌问题可以发现一个性质：必定至少有两个相邻的人不需要从别人那里获得纸牌（这是显然的，不妨设这两个人的位置为$i$和$i+1$，则环形序列中必定有满足条件$a[i]leq T;;a[i+1]geq T$的两个相邻位置，这样$a[i],;a[i+1]$之间没有交换，$a[i]leq T$可以从$a[i-1]$获得纸牌，$a[i+1]geq T$可以把多的纸牌给$a[i+2]$）。
于是由上面的性质，我们直接破环成链，枚举相邻的不需要交换纸牌的两人（将其分别放在第一和最后一个位置）。
按开始的序列顺序，像普通均分纸牌一样处理出$s$数组，那么假设枚举的位置为$k$，则类比普通均分纸牌求法，新的$s[i]=|s[i]-s[k]|$（注意$s$为前缀和），于是$ans=sum{|s[i]-s[k]|}$，我们套用中学数学知识可知当$s[k]$为$s$中位数时，$ans$最小。于是本题就解决了。
代码：
#include<bits/stdc++.h> #define il inline #define ll long long using namespace std; const int N=105; ll n,a[N],sum,s[N]; int main() { ios::sync_with_stdio(0); cin>>n; for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i]; sum/=n; for(int i=1;i<=n;i++)a[i]-=sum,s[i]=s[i-1]+a[i]; sort(s+1,s+n+1); sum=0; for(int i=1;i<=n;i++)sum+=abs(s[n/2+1]-s[i]); cout<<sum; return 0; }