【CodeForces】[348A]Mafia

问题描述

Mafia

[codeforces-348A] [3173291955655301] @vjudge

问题分析

N个人参与一个游戏，每一局都必须有一个人出来当监督，剩下N-1个人当玩家，第i个人要求至少自己要当ai次玩家，请问最少要进行多少次游戏。

根据x次游戏能否打成进行二分查找

对于答案x的判定，先将每个人的要求加起来得到sum，然后判断x*n-sum，如果这个值大于等于x，说明可行，因为这个值就代表这些人可以提供最多的当监督的次数，只要监督的次数能够达到x次，就说明能够进行x次。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<stdio.h>
__int64 n,sum;
bool judge(__int64 x) {
    return x*n-sum>=x;
}
int main() {
    while(scanf("%d",&n)!=EOF) {
        __int64 min=0;
        sum=0;
        for(int i=0; i<n; i++) {
            __int64 t;
            scanf("%I64d",&t);
            sum+=t;
            if(min<t)
                min=t;
        }
        __int64 l=min,r=sum,res;
        while(l<=r) {
            __int64 mid=(l+r)/2;
            if(judge(mid)) {
                res=mid;
                r=mid-1;
            } else
                l=mid+1;
        }
        printf("%I64d\n",res);
    }
    return 0;
}