【AtCoder Regular Contest 079 E】Decrease (Judge ver.)

mrsrz 3月 12, 2020

贪心。

题目大意：

给定 $n$ 个数，需要进行以下操作若干次：

选择最大的数（如果有多个则任意选择），让它减去 $n$，让其他数加上 $1$。

问多少次操作后，最大值小于 $n$。

题解：

由于最大值要小于 $n$，所以如果最大值大于等于 $n$ 时，它必然会进行操作。而且对其他数加 $1$ 的操作，可以在这之后统一进行，不会对前面的操作产生影响。

所以我们不用管“选择最大的数”的条件，直接每次令所有数降到 $n$ 以下即可。这样做完以后再将要加上的数量加上去。如果此时最大值大于等于 $n$ 则继续。

这样最多 $O(\log a)$ 次一定会结束。

Code：

#include<cstdio>
typedef long long LL;
int n;
LL a[55],ans,s,b[55];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%lld",a+i);
    for(;;s=0){
        for(int i=1;i<=n;++i)s+=b[i]=a[i]/n,a[i]%=n;
        if(!s)break;
        ans+=s;
        for(int i=1;i<=n;++i)a[i]+=s-b[i];
    }
    printf("%lld\n",ans);
    return 0;
}