CF1538B Friends and Candies 题解

题目大意

有 \(t\) 组测试数据。

对于每一组测试数据，有 \(n\) 个糖果堆，每个糖果堆都有 \(a_i\) 颗糖果，请问可不可以把所有糖果分平均？

如果可以输出最少要分几次才能平均，不可以就输出 \(-1\)。

思路

2.1 考虑不行的情况

把所有的糖果堆里的糖果数量加在一起得到和 \(sum\)，再平均分给 \(n\) 个糖果堆。如果不能均分即当 \(sum \ mod \ n \neq 0\) 时，输出 \(-1\)。

2.2 考虑可以的情况

可以想一想移多补少的思想。

现在既然 \(sum\ mod \ n=0\)，就可以算一算平均数 \(num\)。 \(num=\frac{sum}{n}\)。

为了移多补少， 就把所有糖果量大于平均数的糖果堆移到糖果量小于平均数的糖果堆里，显然有分糖果的次数等于拥有大于平均数糖果量的糖果堆个数。

• Warning：不要将糖果量等于平均数的糖果堆也算进去了，它们不需要变动。

代码

详情见注释。

#include 
using namespace std;
int t,n,a[200010],cnt;
int ans;
int main(){
	cin>>t;
	while(t--){ //多组数据
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			ans+=a[i]; //求和
		}
		if(ans%n!=0){
			cout<<-1<