＂中国东信杯＂广西大学第二届程序设计竞赛

题目描述

沉迷《原初幻想41》的冒险者Antinomy来到了红玉海——远东之国和奥萨德次大陆之间的中立海域。

Antinomy走到天之御柱前，发现卑微红色职业们正在排队，无聊的在一起玩游戏，由于自己是高贵的蓝色职业，所以Antinomy无法理解他们在玩什么，但是可以看出，他们一共有

但是他们都不想当工具人，而是想参与游戏，其中第 $iii个卑微红想至少参加RiR_iRi个回合的游戏。$

Antinomy想知道他们的游戏至少要进行多少个回合才能满足每个卑微红的要求？

注意，并不是每个卑微红都必须得当一次工具人，如果满足要求，每个人也可以一直当工具人。

输入描述:

第一行输入一个整数

第二行是

nnn个空格分隔的整数，分别表示R1,R2,R3,…RnR_1,R_2,R_3,…R_nR1​,R2​,R3​,…Rn​

imes10^51≤n≤2×105

R_i leq 10^91≤Ri​≤109

输出描述:

输出一行一个整数表示答案

示例1

输入

复制

6
1 1 4 5 1 4

输出

复制

备注:

注意数据范围，C++的printf输出64位long long请使用%lld，unsigned long long请使用 %llu

思路：假设要玩ans局，那么对于每一个卑微红，ans要大于等于他想玩的局数，
如果ans大于卑微红想玩的局数，那么这个卑微红可以当ans-a[i]次工具人，
现在假设ans的值是卑微红中想玩的局数次数的最大值，设定一个值为sum，sum就等于ans-a[i].
如果sum>=ans,意思就是大家当工具人的次数大于局数，那么ans就符合条件，如果sum的值小于ans，也就是当工具人的次数，要小于想玩的局数，
这显然是不符合题意的，那么我们只能让局数加1，也就是ans+1（如何理解局数加1就符合条件了呢，例如极端样例 2 2 2，每个人都想玩两局，按我们的假设，显然ans = 2，但是sum = 0的，也就是说，
如果要是玩两局的话，没有人当工具人来计数，这显然是不符合的，那么就玩三局，在每一局中都让一个人当工具人计数，这就符合条件了）。

具体看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
typedef long long ll;
ll a[N];
int main()
{
    int n;
    cin>>n;
    for(int i = 0; i < n; i++) {
        cin>>a[i];
    }
    sort(a,a+n);        //从小到大排序找出局数最大值
    ll ans = a[n-1];    //先假设玩a[n-1]局
    ll sum = 0;
    for(int i = 0; i < n-1; i++) {
        sum += ans - a[i];  //sum为玩ans局时每个人可以当工具人的次数
    }
    if(sum >= ans) {
        cout<<ans<<endl;
    }
    else{
        cout<<ans+1<<endl;
    }
    return 0
}