分数: 1400 点
问题陈述
有一些带有整数的球 上面写着 1 to N 。 具体来说,有 A_i 带有整数的球 i (1 \leq i \leq N)写在上面。
定义 S=A_1+A_2+\cdots+A_N。 在此,可以保证 S 是正偶数。 划分 S 球进入 S/2 对。 成对的两个球上写的整数必须不同。 可以证明,在该问题的约束下,这样的配对是可能的。
对于每对,执行以下操作:
- 设写在两个球上的整数为 x 和 y (x < y)。 将这些球上写的数字替换为 x+0.5 和 y-0.5。
完成所有对的操作后,让 d 是写有相同数字的球的最大数量。 找到最小可能值 d.
解决 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
- 总和 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
考虑第一个测试用例。 让 (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.