题目链接:http://codeforces.com/problemset/problem/348/A
题目大意:N个人中找出1个人主持,剩下N-1个人参与游戏,给出每个人想参与游戏的次数,问要满足每个人最少要玩多少轮游戏。
我的算法会烦一点:
首先找出所有人中想参与游戏的最大次数max,即可能的最小解ans。
然后用这个max去减每个人想要参与游戏的次数,得到在max次游戏中每个人能够当主持的次数。把这些次数加起来得到b,与max的大小进行比较,如果b>=max则说明满足了每个人人的期望。
否则,ans+1,然后b+n-1,(即除了想参与max次数的人当主持的次数都+1),再进行比较,直到找到b>=m的情况,这时候的ans就是最终结果。
P.S:有多个max的情况也不影响结果。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
long long a[];
long long b[];
int main()
{
int n;
scanf("%d",&n);
int i,j;
long long Max=,all=,ans;
for(i=;i<n;i++)
{
scanf("%I64d",&a[i]);
if(Max<a[i])
{
Max=a[i];
}
}
for(i=;i<n;i++){
b[i]=Max-a[i];
all+=b[i];
}
if(all>Max)
ans=Max;
else
{
ans=Max+(Max-all+n-)/(n-);
}
printf("%d\n",ans);
return ;
}