Codeforces Round #202 C - Mafia

这个题二分做，对于确定x更新次，我们可以确定是否能够更新，如果满足任意a[i]<x && ∑(x-a[i]) >=x就满足情况。对x来说x越大，越快让每个人更新好，这样就有个单调性，就可以用二分来做。 这题也没想到二分做，做题要考虑多方面的解题思路把。说穿了还是题刷的不够多，理解的不够深刻。

/*If I get TLE , it is good.If I get AC,it's NICE !*/ #include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> using namespace std; typedef long long ll; const int MAXN=1e6+100; ll a[MAXN]; ll n; ll judge(ll x) { ll sum=0; for(ll i=1;i<=n;i++) { if(a[i]<=x) sum+=x-a[i]; else return 0; } if(sum<x) return 0; return 1; } int main(void) { cin >> n; for(int i=1;i<=n;i++) scanf("%d",&a[i]); ll left=1,right=1e14,mid; ll ans; while(left <= right) { mid=left+(right-left)/2; if(judge(mid)) ans=mid,right=mid-1; // 对于可行的mid ， 我们往左边区间去找，找尽量小的可行点并保存下来 else left=mid+1; //printf("%I64d-%I64d-%I64d\n",left,right,mid); } //printf("%I64d\n",judge(3)); printf("%I64d\n",ans); }