/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
空でない整数列 x = (x_1, \ldots, x_n) のスコアを，x の要素のうちで x の平均値より大きなものの個数として定めます．
つまり，x のスコアは x_i > \dfrac{x_1+\cdots+x_n}{n} を満たす i の個数です．
長さ N の整数列 A=(A_1,\ldots,A_N) が与えられます． A の空でない部分列に対するスコアの最大値を求めてください．
T 個のテストケースが与えられるので，それぞれについて解いてください．
部分列とは
数列 A の部分列とは，A の要素を 0 個以上選んで削除し，残った要素を元の順序を保って並べた数列のことを指します．制約
- 1\leq T\leq 2\times 10^5
- 2\leq N\leq 2\times 10^5
- 1\leq A_i\leq 10^9
- 入力される値はすべて整数
- すべてのテストケースにわたる N の総和は 2\times 10^5 以下．
入力
入力は以下の形式で標準入力から与えられます．
T
\text{case}_1
\vdots
\text{case}_T
各ケースは以下の形式で与えられます．
N A_1 \cdots A_N
出力
T 行出力してください．i 行目には i 番目のテストケースについて，A の空でない部分列に対するスコアの最大値を出力してください．
入力例 1
3 5 2 6 5 7 5 5 10 10 10 10 10 5 1 10 100 1000 10000
出力例 1
3 0 1
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)：平均値は \dfrac{19}{4}，スコアは 3 です．
- x = (A_1,A_2,A_3,A_4,A_5) = (2, 6, 5, 7, 5)：平均値は 5，スコアは 2 です．
Score : 500 points
Problem Statement
Define the score of a non-empty integer sequence x = (x_1, \ldots, x_n) as the number of elements of x that are strictly greater than the average of x.
That is, the score of x is the count of indices i satisfying x_i > \dfrac{x_1+\cdots+x_n}{n}.
You are given a length-N integer sequence A = (A_1, \ldots, A_N). Find the maximum score of a non-empty subsequence of A.
There are T test cases; solve each one.
Definition of subsequence
A subsequence of A is any sequence obtained by deleting zero or more elements from A and keeping the remaining elements in their original order.Constraints
- 1\le T\le 2\times 10^5
- 2\le N\le 2\times 10^5
- 1\le A_i\le 10^9
- All input values are integers.
- The sum of N over all test cases is at most 2\times 10^5.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\vdots
\text{case}_T
Each case is given in the following format:
N A_1 \cdots A_N
Output
Print T lines. The i-th line should contain the maximum score of a non-empty subsequence of A for the i-th test case.
Sample Input 1
3 5 2 6 5 7 5 5 10 10 10 10 10 5 1 10 100 1000 10000
Sample Output 1
3 0 1
For the first test case, below are examples of subsequences, their averages, and their scores.
- x = (A_1) = (2): the average is 2, and the score is 0.
- x = (A_3,A_5) = (5,5): the average is 5, and the score is 0.
- x = (A_1,A_3,A_4,A_5) = (2,5,7,5): the average is \frac{19}{4}, and the score is 3.
- x = (A_1,A_2,A_3,A_4,A_5) = (2,6,5,7,5): the average is 5, and the score is 2.