← 返回题目列表

AtCoder · awtf2025_c

C. 靠近一点

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

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