A21578.负载平衡问题 题解

其实这题和A118挺像的，只不过那题是一条链，而这题是一个环，但是思想都一样，都是用平均数来做文章。

想象一堆牌围成一圈，在脑中模拟分牌过程，你会发现一个性质：必定至少有两堆相邻的牌不需要从别的纸牌堆那里获得纸牌。

于是，我们可以利用这个性质，把环破坏成链，枚举不需要交换纸牌的那两堆纸牌，将其分别放在链的第一个位置与最后一个位置。

最后按开始的序列顺序，像普通均分纸牌一样预处理出 $b$ 数组。设枚举的位置为 $k$，平均数为 $sum$，$b_i$设为 $a_i-sum$ 的前缀和，则题目就是求 $ans=\sum \left|b_k-b_i\right|$ 的最小值了。根据初中的知识可得当 $k$ 为 $\frac{n+1}{2}$ 时 $ans$ 的值最小。

#include<bits/stdc++.h>
using namespace std;
int n,a[1000001],sum,b[1000001];
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(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,b[i]+=b[i-1]+a[i];
	sort(b+1,b+1+n);
	sum=0;
	for(int i=1;i<=n;i++)sum+=abs(b[(n+1)/2]-b[i]);
	cout<<sum;
	return 0;
}

建议将为普及- 或者 普及/提高-，这题并不难。