C++ 一共r个人周坐在圆桌前,现有梨r的整数倍人。每个人都相互谦让,把自己多的梨分给左右手第一位的人们,这样最终一定可以让每个人得到一样多的梨。求给出去的梨的最小值。 [输入]输入包含多组数据,每组数据第一行为整数<1000000),以下行每行为一个整数,按逆时针顺序给出初始时每个人对应的梨数。 [输出]对于每组数据,输出被送出的梨的最小值
时间: 2024-03-04 17:51:21 浏览: 28
这是一道比较典型的数学问题,需要运用到数论中的一些知识。
首先,由于每个人最后得到的梨数相同,所以圆桌上所有人的梨数之和必定是梨数的整数倍,即 $\sum_{i=1}^{r} a_i$ 是 $r$ 的整数倍。
其次,我们可以假设最终每个人得到的梨数为 $x$,那么每个人最终应该有 $x-a_i$ 个梨,其中 $a_i$ 是初始时第 $i$ 个人的梨数。如果 $x-a_i$ 是负数,说明这个人需要向左右两边的人要梨,如果是正数,说明这个人需要向左右两边的人分梨。因此,我们可以计算出初始时所有人需要向左右两边分的梨的总数 $s=\sum_{i=1}^{r} \max(0, x-a_i)$。
最后,如果 $s\leq xr$,说明每个人最多只需要分出一个梨,因此最小的被送出的梨的数量为 $1$。否则,我们可以二分答案 $ans$,然后根据上面的方法,计算出 $s$,如果 $s\leq ansr$,说明可以让每个人得到 $ans$ 个梨,否则需要分出更多的梨。最后得到的最小的满足条件的 $ans$ 就是答案。
具体实现可以参考以下代码: