E - Mafia CodeForces - 348A 【二分】

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个人，其中每个人最少参加ai次比赛。比赛是这样定义的：n个人之中出1个裁判，其中n-1个人参加

问：最少需要多少场比赛可以满足所有人要求？

思路：

因为每一局裁判只有一个，因此把焦点聚集身上在裁判，不要聚集在玩家身上

假设一共玩了k局，那么某个人当裁判的局数最多就是k-a[i]
，(就是他玩够之后一直都在当裁判），把所有人当裁判的最大值加起来，如果总值大于等于k，说明每一场比赛都可以找到裁判，（意味着k是可以的），当前k可以就减小k（左移），当前k不可以就增加k（右移）

也就是n * k - sum > k就表示该k值可以，也就是sum / (n - 1)向上取整，但是要注意这个值有可能会小于a[i]的最大值，也就是有的人的要求不能满足，因此还要将该值和a[i]max比较，取较大值。

AC代码如下：【二分】

#include <iostream>
#include <stdio.h>
#include <math.h>
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;
const int maxn = 100005;
long long a[maxn];
int n;

bool c(long long x)
{
    long long sum = 0;
    for(int i = 0; i < n; i++)
    {
        if(x < a[i])//局数小于玩家想玩的次数 不行
            return false;
        else
            sum += (x - a[i]);
    }
    if(sum >= x)//所有玩家当裁判的最大值的和大于局数 意味着可以找到裁判 局数符合要求 但不一定是最小的符合要求的局数 所以需要二分
        return true;
    else
        return false;
}

void sol()
{
    long long l = 0, r = maxn * 1e9;
    while(r - l > 1)
    {
        long long mid = (r - l) / 2 + l;
        if(c(mid))
            r = mid;
        else
            l = mid;
    }
    cout<<r<<endl;
}

int main()
{
   while(~scanf("%d", &n))
   {
       for(int i = 0; i < n; i++)
       {
           cin>>a[i];
       }
       sol();
   }
   return 0;
}

AC代码如下：【数学简化】

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <math.h>

using namespace std;
const int maxn = 100010;
long long a[maxn], ma;
int n;

int main()
{
    while(~scanf("%d", &n))
    {
        ma = -1;
        long long sum = 0, ans = 0;
        for(int i = 0; i < n; i++)
        {
            cin >> a[i];
            sum += a[i];
            ma = max(a[i], ma);
        }
        ans = (sum + n - 2) / (n - 1);
        ans = max(ans, ma);
        cout<<ans<<endl;
    }
    return 0;
}