題干：

One day?n?friends gathered together to play "Mafia". During each round of the game some player must be the supervisor and other?n?-?1?people take part in the game. For each person we know in how many rounds he wants to be a player, not the supervisor: the?i-th person wants to play?ai?rounds. What is the minimum number of rounds of the "Mafia" game they need to play to let each person play at least as many rounds as they want?

Input

The first line contains integer?n?(3?≤?n?≤?105). The second line contains?n?space-separated integers?a1,?a2,?...,?an?(1?≤?ai?≤?109)?— the?i-th number in the list is the number of rounds the?i-th person wants to play.

Output

In a single line print a single integer — the minimum number of game rounds the friends need to let the?i-th person play at least?ai?rounds.

Please, do not use the?%lld?specifier to read or write 64-bit integers in С++. It is preferred to use the?cin,?cout?streams or the?%I64d?specifier.

Examples

Input

3 3 2 2

Output

4

Input

4 2 2 2 2

Output

3

Note

You don't need to know the rules of "Mafia" to solve this problem. If you're curious, it's a game Russia got from the Soviet times:?http://en.wikipedia.org/wiki/Mafia_(party_game).

題目大意：

? ? ?n個人玩游戲，告訴你游戲規則：每輪游戲會有1個裁判，剩下n-1個人當參與者。已知第i個人要求當ai次參與者。。問你至少幾輪游戲可以讓所有人都心滿意足。

解題報告：

? ?二分輪數。如果滿足的話，我們讓每個人，除了那ai次當參與者，剩下的都當裁判去，如果此時當的裁判數大于輪數，說明這種輪數就可以，（因為我可以讓那些多的人在去當參與者嘛，反正他們不嫌多）然后就可以二分了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; ll a[MAX]; int n; bool ok(ll x) {ll sum = 0;for(int i = 1; i<=n; i++) sum += (x-a[i]);return sum >= x;} int main() {ll l = 0,r = 1e13;cin>>n;for(int i = 1; i<=n; i++) scanf("%lld",a+i),l=max(l,a[i]);ll mid = (l+r)>>1,ans = 0;while(l<=r) {mid=(l+r)>>1;if(ok(mid)) {ans=mid;r=mid-1;}else l=mid+1;}printf("%lld\n",ans);return 0 ;}

兩個注意事項：

? ?1.r不能開太大，不能1e13，，因為在ok函數中會越界變成負數就GG了，，所以1e13剛好滿足：1e5的n去乘上ok函數中極限狀態的x（也就是r的最大取值）要小于longlong的范圍、、、所以1e13就很合適、、不能想當然的開個最大1e18！！就炸了！！

? ?2.l不能從0開始取值，而應該從a[i]的最大值? 開始。因為如果要從0開始取值，，ok函數中就需要判斷如果有一個a[i]<x了就得return 0；因為這就不滿足題意，是不可取的輪數！！所以方便起見就在初始化的時候設置好了。。這個和 修路 的那道題 是完全一樣的想法。。要先去掉一部分l，，，不要從0開始取，，不然還得在ok函數中return掉，就很麻煩、。（當然也可以AC）

在此也做個總結，二分答案驗證的時候，首先要看你的答案 需要滿足題目中哪些信息，，然后再決定ok函數中怎么寫來一定可以滿足這些條件，，比如這個題，幾個要求：首先每個人一定要當ai次參與者，剩余的輪數可以隨便（也可以當參與者也可以當裁判）其次我要能夠成功舉辦x輪游戲，說明我至少有x個裁判。滿足兩者點，我們就可以return 1? 了。想想其實也不難，是不。

其實啊這題也可以直接O(1)出結果的。因為你看啊其實每次你都在做相同的工作，每次ok函數中都是減掉了所有的a[i]，所以直接在main函數中求一個sum=(a[1]+a[2]+....+a[n])。然后求一個方程nx-sum >= x，求解x的最小值就可以了、、、所以啊沒必要二分的、、二分就感覺怪怪的，就跟二分求a+b一樣。

總結

以上是生活随笔為你收集整理的【CodeForces - 349C】Mafia（思维模拟，优秀的二分）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。