C - Get Closer Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 1400 点

問題文

1 以上 N 以下の整数が書かれたボールがあります． 具体的には，整数 i (1 \leq i \leq N) の書かれたボールが A_i 個あります．

S=A_1+A_2+\cdots+A_N と定義します． ここで，S が正の偶数であることが保証されます． S 個のボールを S/2 個のペアに分けます． ペアになった 2 つのボールに書かれた整数は異なる必要があります． なお，この問題の制約下でこのようなペア分けが可能であることが証明できます．

各ペアについて，以下の操作を行います．

  • 2 つのボールに書かれた整数がそれぞれ x,y (x < y) であるとする． これらのボールに書かれている数を，それぞれ x+0.5,y-0.5 で置き換える．

すべてのペアについて操作を終えたあと，同じ数が書かれているボールの個数の最大値を d とおきます． d としてありうる最小値を求めてください．

1 つの入力につき，T 個のテストケースを解いてください．

制約

  • 1 \leq T \leq 125000
  • 2 \leq N \leq 250000
  • 0 \leq A_i \leq 10^9
  • S=A_1+A_2+\cdots+A_N は正の偶数である
  • A_i \leq S/2
  • 1 つの入力における N の総和は 250000 を超えない
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

T
case_1
case_2
\vdots
case_T

各テストケースは以下の形式で与えられる．

N
A_1 A_2 \cdots A_N

出力

各テストケースに対し，答えを出力せよ．

入力例 1

4
4
1 2 2 1
4
2 2 5 1
7
101 2 203 304 5 106 107
20
239276621 320064891 910500852 164832983 245532750 198319686 715892722 967824729 769431650 80707349 459924867 257261830 777045523 583882654 950300098 438099970 322288793 532405019 256358887 45539860

出力例 1

2
6
203
613287276

1 つ目のテストケースについて考えます． 整数 x,y の書かれたボールのペアを (x,y) で表すことにします．

例えば，(1,3),(2,3),(2,4) とペア分けすると，操作後にボール書かれている数は 1.5,2.5,2.5,2.5,2.5,3.5 になります． 同じ数が書かれているボールの個数の最大値は d=4 です．

一方，(1,2),(2,3),(3,4) とペア分けすると，操作後にボール書かれている数は 1.5,1.5,2.5,2.5,3.5,3.5 になります． 同じ数が書かれているボールの個数の最大値は d=2 となります．

d を 2 より小さくすることはできないので，2 が答えになります．

Score : 1400 points

Problem Statement

There are balls with integers from 1 to N written on them. Specifically, there are A_i balls with integer i (1 \leq i \leq N) written on them.

Define S=A_1+A_2+\cdots+A_N. Here, it is guaranteed that S is a positive even number. Divide the S balls into S/2 pairs. The integers written on the two balls in a pair must be different. It can be proved that such pairing is possible under the constraints of this problem.

For each pair, perform the following operation:

  • Let the integers written on the two balls be x and y (x < y). Replace the numbers written on these balls with x+0.5 and y-0.5, respectively.

After completing the operation for all pairs, let d be the maximum number of balls with the same number written on them. Find the minimum possible value of d.

Solve T test cases for each input.

Constraints

  • 1 \leq T \leq 125000
  • 2 \leq N \leq 250000
  • 0 \leq A_i \leq 10^9
  • S=A_1+A_2+\cdots+A_N is a positive even number.
  • A_i \leq S/2
  • The sum of N over all test cases in each input does not exceed 250000.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each test case is given in the following format:

N
A_1 A_2 \cdots A_N

Output

For each test case, output the answer.

Sample Input 1

4
4
1 2 2 1
4
2 2 5 1
7
101 2 203 304 5 106 107
20
239276621 320064891 910500852 164832983 245532750 198319686 715892722 967824729 769431650 80707349 459924867 257261830 777045523 583882654 950300098 438099970 322288793 532405019 256358887 45539860

Sample Output 1

2
6
203
613287276

Consider the first test case. Let (x,y) denote a pair of balls with integers x,y written on them.

For example, if we pair as (1,3),(2,3),(2,4), the numbers written on the balls after the operation are 1.5,2.5,2.5,2.5,2.5,3.5. The maximum number of balls with the same number written on them is d=4.

On the other hand, if we pair as (1,2),(2,3),(3,4), the numbers written on the balls after the operation are 1.5,1.5,2.5,2.5,3.5,3.5. The maximum number of balls with the same number written on them is d=2.

d cannot be made smaller than 2, so the answer is 2.