Game of Ball Passing
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int a[N];
int main()
{
int t;
cin>> t;
while(t--)
{
int n;
cin>> n;
long long sum=0;
bool x=true;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]!=0)x=false;
sum+=a[i];
}
sort(a,a+n);
sum-=a[n-1];
if(x){
cout<<0<<endl;
continue;
}
else if(a[n-1]-1-sum>0)
{
cout<<(a[n-1]-sum)<<endl;
}
else cout<<1<<endl;
}
}
将每人的传球次数视作每个人的使用机会 ，使用机会来串成几串，每串的最后一位不占使用次数
那么怎么串才能得到最小的串数呢？要得到最小的串数，就要把每个串尽可能的延长。如果要尽
可能的将串延长，就要看使用次数最多的有几个空位。如果空位数少于其他人的使用次数总和，
那就说明一条串就足够了，因为空位中可以塞不止一个人。如果空位数大于其他人的使用次数总
和，就说明一条串不够用，还需a[n-1]-sum-1个串。
京东工作强度 243人发布