牛客题霸CodeForces(Div 1) 348AMafia题解

按照模拟思路，我们每次操作要考虑每一回合哪些n-1个人要进行游戏 。

但是我们不如逆向思维，每一回合我们都只需要一个观察者，那么我们此时最多可以玩多少回合呢？

要使回合数最多，那么就是让这个人玩够了就去一直当裁判

所以最多回合数就是（当前要玩的回合数-第i个人想要玩的局数）

最后如果这个最多回合数大于等于当前要进行的回合数，就可以保证每一回合都有人当裁判，这个回合数也就可行。

代码

#include<iostream>
#include<algorithm>
using namespace std;
long long n;
long long gamers[100005];
bool check(long long x){
    long long sum=0;
    for(int i=0;i<n;i++){
        sum+=x-gamers[i];
    }
    return sum>=x;
}
int main(void){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>gamers[i];
    }
    sort(gamers,gamers+n);
    long long left=gamers[n-1],right=0x3f3f3f3f3f3f;
    while(left<=right){
        long long mid = (left+right)>>1;
        if(check(mid)){
            right=mid-1;
        }
        else
        {
            left=mid+1;
        }
    }
    cout<<left<<endl;
    return 0;
}