题解 CF1452B 【Toy Blocks】
Published:
观察样例，首先得到一个结论，所有数的总和必须是 $n-1$ 的倍数，这是本题的第一个限制条件。接下来考虑第二个限制条件，我们如何让每个数达到相同，思考极端情况，最麻烦的情况，就是还剩一个最大值的情况，即，我们至少要将其他数全部变为这个最大值，而一旦满足这个条件，其他条件都非常好实现。因此，我们取满足这两个条件的最小值即可。
#include<bits/stdc++.h>
#define re register
#define ll long long
#define LL inline ll
#define I inline int
#define V inline void
#define B inline bool
#define FOR(i,a,b) for(re int i=(a),i##i=(b);i<=i##i;++i)
#define ROF(i,a,b) for(re int i=(a),i##i=(b);i>=i##i;--i)
#define gc getchar()
using namespace std;
const int N=1e5+10;
LL read(){
ll p=0; bool w=0; char ch=gc;
while(!isdigit(ch)) w=ch=='-'?1:0,ch=gc;
while(isdigit(ch)) p=p*10+ch-'0',ch=gc;
return w?-p:p;
}
int T,n;
ll ans,mx,a[N],sum;
int main(){
T=read();
while(T--){
n=read(),mx=0,sum=0;
FOR(i,1,n) a[i]=read(),sum+=a[i],mx=max(mx,a[i]);
if(sum%(n-1)) ans=(sum/(n-1)+1)*(n-1);
else ans=sum;
ans=max(ans,mx*(n-1));
cout<<ans-sum<<endl;
}
return 0;
}