https://codeforces.com/gym/104493/problem/J 题意： 加入一个最小的X，使得均值和平均数相等 思路： 考虑a[n/2],a[n/2+1],x作为平均数的情况 waon17

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+100;
int t,n,a[N];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0); 
	cin>>t;
	while(t--)
	{
		int sum=0;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			sum+=a[i];
		}
		sort(a+1,a+1+n);
		int wan,ans=LLONG_MAX;
		wan=a[n/2]*(n+1);
		if(wan-sum<=a[n/2])
		{
			ans=min(ans,wan-sum);
		}
		wan=a[n/2+1]*(n+1);
		if(wan-sum>=a[n/2+1])
		{
			ans=min(ans,wan-sum);
		}
		if(sum%n==0)
		{
			wan=sum/n;
			if(wan>=a[n/2]&&wan<=a[n/2+1])
			{
				ans=min(ans,wan);
			}
		}
		cout<<ans<<endl;
		//x*n+1=sum+x
		//x*n=sum
	}
	return 0;
}