题意
在网络流 24 题中隐藏的环形均分纸牌问题
分析
考虑普通均分纸牌问题
第 (i) 个人有 (a_i) 张牌,总牌数为 (sum=sum_{i=1}^na_i),均分下来的牌数为 (T=frac{sum}{n}).
于是每个人与平均值的差为 (d_i= T-a_i). 如果要让 (a_i) 变成 (T),就让 (a_i+=d_i,a_{i+1}-=d_i).
所以令 (s_i=sum_{j=1}^id_j),表示第 (i) 个人的吞吐量,那么让前 (k) 个人变成 (T) 的分牌次数为 (sum_{i=1}^k|s_i|).
这是一个定值
考虑环形均分
环形中,必存在 (kin[1,n],a_kleq T,a_{(k+1)mod n}geq T).
因此前者从前面获得纸牌,后者向后面推送纸牌
于是破环为链计算即可
于是双倍一下
那么第 (k+1) 到 (k+n) 的均分数为
[egin{split}
&sum_{i=k+1}^{k+n}left|sum_{j=k+1}^id_j
ight|\
=&sum_{i=k+1}^{k+n}left| sum_{j=1}^id_j- sum_{j=1}^kd_j
ight|\
=&sum_{i=k+1}^{k+n}left| s_i-s_k
ight|\
end{split}
]
代码
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200;
int n,sum,t,ans=0x3f3f3f3f;
int a[N*2],d[N*2],s[N*2],g[N*2];
int abs(int x){return x>0?x:-x;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum+=(a[i+n]=a[i]);
t=sum/n;
for(int i=1;i<=n*2;i++)d[i]=t-a[i];
for(int i=1;i<=n*2;i++)s[i]=s[i-1]+d[i];
for(int i=1;i<=n;i++){
int tot=0;
for(int j=1;j<=n;j++)tot+=abs(s[i+j]-s[i]);
ans=min(ans,tot);
}
printf("%d",ans);
return 0;
}