← 返回题目列表

Codeforces · 1529/A

A. Eshag 喜欢大数组

中文机器翻译题面 查看原题

Eshag 有一个由 $$$n$$$ 整数组成的数组 $$$a$$$。

Eshag 可以多次执行以下操作:选择 $$$a$$$ 的某个子序列,并删除其中严格大于 $$$AVG$$$ 的每个元素,其中 $$$AVG$$$ 是所选子序列中数字的平均值。

例如,如果$$$a = [1 , 4 , 3 , 2 , 4]$$$并且Eshag将操作应用于包含$$$a_1$$$、$$$a_2$$$、$$$a_4$$$和$$$a_5$$$的子序列,那么他将删除这些$$$4$$$中大于的元素$$$\frac{a_1+a_2+a_4+a_5}{4} = \frac{11}{4}$$$,所以运算后,数组$$$a$$$将变为$$$a = [1 , 3 , 2]$$$。

你的任务是通过应用上述操作一定次数(可能是零次)来找到 Eshag 可以从数组 $$$a$$$ 中删除的最大元素数。

如果 $$$b$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$c$$$ 获得,则序列 $$$b$$$ 是数组 $$$c$$$ 的子序列。

输入

第一行包含一个整数 $$$t$$$ $$$(1\le t\le 100)$$$ — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ $$$(1\le n\le 100)$$$ — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ $$$(1\le a_i \le 100)$$$ — 数组 $$$a$$$ 的元素。

输出

对于每个测试用例,打印一个整数 - Eshag 可以从数组 $$$a$$$ 中删除的最大元素数。

示例

输入 #1

3
6
1 1 1 2 2 3
6
9 9 9 9 9 9
6
6 4 1 1 4 1

输出 #1

3
0
3

注意

考虑第一个测试用例。

最初 $$$a = [1, 1, 1, 2, 2, 3]$$$。

在第一个操作中,Eshag 可以选择包含 $$$a_1$$$、$$$a_5$$$ 和 $$$a_6$$$ 的子序列,它们的平均值等于 $$$\frac{a_1 + a_5 + a_6}{3} = \frac{6}{3} = 2$$$。因此 $$$a_6$$$ 将被删除。

之后 $$$a = [1, 1, 1, 2, 2]$$$。

在第二个操作中,Eshag 可以选择包含整个数组 $$$a$$$ 的子序列,其所有元素的平均值等于 $$$\frac{7}{5}$$$。因此 $$$a_4$$$ 和 $$$a_5$$$ 将被删除。

之后 $$$a = [1, 1, 1]$$$。

在第二个测试用例中,Eshag 无法删除任何元素。