分数: 500 点
问题陈述
定义 非空整数序列的 分数 $$$v$$$ 的 非空整数序列的 x = (x_1, \ldots, x_n) 作为元素的数量 x 严格大于平均值 x.
即分数 x 是索引的计数 i 满意 x_i > \dfrac{x_1+\cdots+x_n}{n}.
给你一个长度-N 整数序列 A = (A_1, \ldots, A_N)。求非空子序列的最大分数 A.
有 T 测试用例;逐一解决。
子序列的定义
的子序列 A 是通过删除零个或多个元素而获得的任何序列 A 并保持其余元素的原始顺序。约束
- 1\le T\le 2\times 10^5
- 2\le N\le 2\times 10^5
- 1\le A_i\le 10^9
- 所有输入值均为整数。
- 总和 N 所有测试用例最多 2\times 10^5.
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\vdots
\text{case}_T
每个案例均按以下格式给出:
N A_1 \cdots A_N
输出
打印 您选择的 T 行。的 i- 第行应包含非空子序列的最大分数 A 为 i- 第一个测试用例。
示例输入 1
3 5 2 6 5 7 5 5 10 10 10 10 10 5 1 10 100 1000 10000
示例输出 1
3 0 1
对于第一个测试用例,下面是子序列、它们的平均值和分数的示例。
- x = (A_1) = (2):平均值为 2,得分为 0.
- x = (A_3,A_5) = (5,5):平均值为 5,得分为 0.
- x = (A_1,A_3,A_4,A_5) = (2,5,7,5):平均值为 \frac{19}{4},得分为 3.
- x = (A_1,A_2,A_3,A_4,A_5) = (2,6,5,7,5):平均值为 5,得分为 2.