← 返回题目列表

AtCoder · arc197_b

B. 高于平均水平

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

分数: 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.