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

Question

我正在解决来自 codeforces practice problem achieve 的问题。我找不到有效的解决方案。如何解决以下问题？只能想到暴力破解

Polycarpus 有一个数组，由 n 个整数 a1, a2,⟩...,⟩an 组成。 Polycarpus 喜欢数组中的数字匹配。这就是为什么他希望数组具有尽可能多的相等数字。为此，Polycarpus 多次执行以下操作:

他选择数组ai的两个元素，aj(i⟩≠⟩j)；他同时将数ai加1，同时将数aj减1，即执行ai⟩=⟩ai⟩+⟩1和aj = aj⟩-⟩1。给定的操作正好改变了两个不同的数组元素。 Polycarpus 可以无限次地应用所描述的操作。

现在他想知道，如果他执行任意次数的此类操作，他最多可以获得多少个相等的数组元素。帮助 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 then n else n-1

编辑:解释:

首先很容易看出答案是最小n-1，不能再小了。

证明:选择你想做的任何数字作为你的目标。假设最后一个索引 n。现在你通过对 a1 和 an 应用操作使 a1 = 目标。类似地对 a2 和 an 等等。所以所有数字除了最后一个等于目标。

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