GitBook

这里写图片描述

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

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

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

#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;
}

题目地址:【CodeForces】[348A]Mafia