数组中相等元素的最大数量
我正在解决codeforces实践中的问题实现。我找不到有效的解决方案。如何解决以下问题？我只能想到一个暴力解决方案
Polycarpus有一个数组，由n个整数a1， a2， ...， an组成。Polycarpus喜欢数组中的数字匹配。这就是为什么他希望数组有尽可能多的相等的数字。为此，Polycarpus多次执行以下操作：
他选择数组ai的两个元素aj (i ≠ j)；他同时将数字ai增加1，并将数字aj减少1，即执行ai = ai + 1 ≠ aj = aj - 1。给定的操作恰好更改了两个不同的数组元素。Polycarpus可以无限次地应用所描述的操作。
现在他想知道如果他执行任意数量的这样的操作，他可以获得的相等数组元素的最大数量。帮帮波卡普斯。
输入第一行包含整数n (1 ≤ n ≤ 105) -数组大小。第二行包含空格分隔的整数a1， a2， ...， an (|ai| ≤ 104) -原始数组。
输出打印一个整数-如果他执行任意数量的给定操作，他可以获得的相等数组元素的最大数量。
Sample test(s)
input
2
2 1
output
1
input
3
1 4 1
output
3回答 1
Stack Overflow用户
发布于 2012-11-22 00:27:17
求出所有元素的总和。
如果sum%n==0，则n否则n-1
编辑:说明：
首先，很容易发现答案是最小n-1，不能小于n-1。
证明:选择任何你想要做为你的目标的数字假设最后一个索引，你通过在a1上应用操作，在an.Similarly上做a1=target，在a2和an上应用操作，所以on.So，除了最后一个之外，所有的数字都等于n.Now。
现在我们需要看到，如果sum%n==0，那么所有数字都是平均值，您可以选择您的目标作为here.You可以应用的所有数字的平均值，方法是选择一个值小于mean的索引和其他值大于mean的索引，并使其中一个(可能两者)等于mean。
https://stackoverflow.com/questions/13497625
复制相似问题
腾讯云开发者
