ARC079C

StеlІаwіnD · 2022-05-05 19:39:13 · 题解

题面

没说更好的阅读体验

Description:

给你 n 个整数 a_i。每次可以选择一个数，进行以下操作：

• 将该数减小 n。
• 将其他数增加 1。

问至少几次操作才能让所有数均 <n。

对于每次操作给他换个方式描述，变为：

• 将该数减小 n+1。
• 将所有数增加 1。

这样的话，在已知操作次数为 k 的时候，我们可以算出第 i 个数要减少的次数为 \dfrac{a_i-n+k+1}{n+1}。将每个数的操作次数加起来，和最初的 k 进行比较，我们就能判断出操作次数为 k 是否成立。

这明显是一个 \text{check} 函数，很快想到二分 k。然后这个题目就做完了。

代码