Educational Codeforces Round 98

B. Toy Blocks
思维题：随机把某一个箱子里面的积木分给其他箱子等价于sum/(n-1),再比较这个平均值和最大值，选出最大的

#include<bits/stdc++.h>

using namespace std;

int a[100005];

const int INF=0x3f;

typedef long long ll;

int main(){

    int t;

    cin>>t;

    while(t--){

        int n;

cin>>n;

ll sum=0;

int maxv=-INF;

memset(a,0,sizeof(a));

for(int i=1;i<=n;i++){

cin>>a[i];

sum+=a[i];

maxv=max(maxv,a[i]);

}

int mean=0;

if(sum%(n-1)==0) mean=sum/(n-1)

else mean=sum/(n-1)+1;

ll res=max(maxv,mean);

cout<<res*(n-1)-sum<<endl;

    }

    return 0;

}