algorithm - 数组中相等元素的最大数量

Question

我正在解决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

Answer 1

求所有元素的总和。

如果总和%n==0 则 n 否则 n-1

编辑：说明：

首先，很容易发现答案是最小值 n-1。它不能更小。

证明：选择您希望作为目标的任何数字。假设最后一个索引n。现在您通过对a1和an应用操作来制作a1 = target。类似地对a2和an等等。所以除了最后一个之外的所有数字一个等于目标。

现在我们需要看到，如果 sum%n==0 则所有数字都是可能的。显然，您可以在这里选择目标作为所有数字的平均值。您可以通过选择值小于平均值的索引和其他索引来应用操作值大于平均值并使其中之一（可能两者）等于平均值​​。