CF1610E AmShZ and G.O.A.T.

我们称一个长度为 $k$ 的整数数组 $c_1, c_2, \ldots, c_k$ 是“terrible”的，如果满足以下条件： - 设 $AVG = \frac{c_1 + c_2 + \ldots + c_k}{k}$（即数组所有元素的平均值，不一定为整数）。数组中严格大于 $AVG$ 的元素个数要严格多于严格小于 $AVG$ 的元素个数。注意，等于 $AVG$ 的元素不计入统计。 例如，$c = \{1, 4, 4, 5, 6\}$ 是 terrible 的，因为 $AVG = 4.0$，第 $5$ 个和第 $4$ 个元素大于 $AVG$，第 $1$ 个元素小于 $AVG$。 我们称一个长度为 $m$ 的整数数组 $b_1, b_2, \ldots, b_m$ 是“bad”的，如果它存在至少一个非空子序列是 terrible 的；否则称其为“good”。 现在给定一个长度为 $n$ 的整数数组 $a_1, a_2, \ldots, a_n$，请你求出最少需要删除多少个元素，使得剩下的数组是 good 的。 一个数组是另一个数组的子序列，指的是可以通过删除若干（可能为零或全部）元素得到。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示数组 $a$ 的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$ 的元素。 对于每个测试用例，保证 $1 \le i < n$ 时都有 $a_i \le a_{i+1}$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示最少需要删除多少个元素才能使数组变为 good。

在第一个样例中，数组 $a$ 已经是 good 的。 在第二个样例中，只需删除 $1$，得到数组 $[4, 4, 5, 6]$，它是 good 的。 由 ChatGPT 4.1 翻译